C++ Algorithms: Frequency Counting, ISBN Validation, and Horner's Method

Counting Frequencies Algorithm in C++

This C++ implementation demonstrates a method for counting the frequencies of input integers while maintaining a sorted list of unique values. It utilizes custom functions for insertion and shifting elements.

Data Structure Definition

#include <iostream>
#include <vector>
using namespace std;

struct lon{
    int dig, vez; // digit, count (vezes)
};

Helper Functions: Shifting and Positioning

The mover function shifts elements to make space for a new insertion, and donde_poner finds the correct sorted position for a new digit.

void mover(vector<lon>& a, const int& pos, const int& ini){
    for(int i = pos; i > ini; --i){
        a[i].dig = a[i-1].dig;
        a[i].vez = a[i-1].vez;
    }
}

int donde_poner(const vector<lon>& b, int val, int ast){
    int i;
    for(i = 0; b[i].dig < val and i < ast; ++i){
    }
    return i;
}

Main Frequency Counting Logic

int main(){
    int n;
    cin >> n;
    vector<lon> num(n);
    int p = 0;
    for(int i = 0; i < n; ++i){
        if(p == 0){
            cin >> num[p].dig;
            num[p].vez = 1;
            ++p;
        }
        else{
            bool trobat = false; // found
            int act; // current value
            cin >> act;
            for(int j = 0; not trobat and j < p; ++j){
                trobat = num[j].dig == act;
                if(trobat) ++num[j].vez;
            }
            if(not trobat){
                int pos;
                pos = donde_poner(num, act, p);
                mover(num, p, pos);
                num[pos].dig = act;
                num[pos].vez = 1;
                ++p;
            }
        }
    }
    for(int i = 0; i < p; ++i){
        cout << num[i].dig << " : " << num[i].vez << endl;
    }
}

ISBN Validation and Check Digit Calculation

This program reads an ISBN-10 sequence (which may contain '?' for a missing digit or 'X' for the check digit 10) and calculates the missing digit required for a valid ISBN checksum (modulo 11).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<char> v(10);
    int index;
    while(cin >> v[0]) {
        int suma = 0;
        for(int i = 1; i < 10; ++i) cin >> v[i];
        
        // Calculate weighted sum and identify the missing index
        for(int i = 0; i < 10; ++i){
            if(v[i] != '?' and v[i] != 'X') suma += (v[i] - '0') * (10 - i);
            else if (i == 9 and v[i] == 'X') suma += 10;
            else index = 10 - i; // index holds the weight (1 to 10) of the missing digit
        }
        
        bool found = false;
        // Iterate through possible values (0-9, or 10 represented by X)
        for(int i = 0; i <= 10 and not found; ++i) {
            // Check if (current sum + (possible digit * weight)) % 11 == 0
            if((suma + (i * index)) % 11 == 0) {
                found = true;
                if(i == 10) cout << "X" << endl;
                else cout << i << endl;
            }
        }
    }
}

Polynomial Evaluation using Horner's Method

Horner's method provides an efficient way to evaluate a polynomial given its coefficients and a value x. This implementation uses a function avalua (evaluate) to perform the calculation, minimizing the number of multiplications required.

Evaluation Function

#include <iostream>
#include <vector>
using namespace std;

int avalua(const vector<int>& p, int x) {
    int suma = 0;
    int n = p.size();
    // Iterating from the highest degree coefficient down
    for (int i = n - 1; i >= 0; --i) {
        suma = suma * x;
        suma = suma + p[i];
    }
    return suma;
}

Main Program Structure

Note: The input reading loop in the main function below is logically flawed as p.size() is 0 initially. This code snippet focuses on demonstrating the function call structure.

int main() {
    vector<int> p;
    // Input reading (requires correction for practical use)
    for (int i = 0; i < p.size(); ++i) cin >> p[i]; 
    
    int x;
    cin >> x;
    int res = avalua(p, x);
    cout << res << endl;
}

Checking for Odd Sum Pairs in a Sequence

This algorithm determines if a sequence of integers contains at least one pair of adjacent elements whose sum is odd. An odd sum implies that one element is even and the other is odd.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        
        // Read sequence elements
        for (int i = 0; i < n; ++i) cin >> v[i];
        
        bool condicio = false; // condition met
        
        // Check adjacent pairs
        for (int i = 1; i < n; ++i) {
            int suma = v[i] + v[i-1];
            
            // If sum is odd (suma % 2 == 1), the condition is met
            if (suma % 2 == 1) condicio = true;
            else condicio = false; 
            
            if (condicio) i = n; // Early exit optimization
        }
        
        if (condicio) cout << "si" << endl; // yes
        else cout << "no" << endl; // no
    }
}