Счастливые билеты, решить через функцию C++

Question

Задачка про счастливые билеты, соответственно надо найти количество таких 6-ти значных билетов, у которых суммы трёх первых и последних цифр равны. Надо написать функцию, проверяющую, равны суммы или нет. Я написал такой код(исправлено), но после запуска, программа ничего не выводит. Что делать?

#include <iostream>
#include <vector>

using namespace std;
// функция, проверяющая суммы
int summ_6(vector<int>& vec, int sum1, int sum2) {
    for (int i = 0; i < vec.size() / 2; i++) {
        sum1 += vec[i];
    }
    for (int i = vec.size() / 2; i < vec.size(); i++) {
        sum2 += vec[i];
    }
    if (sum1 == sum2) {
        return true;
    }
    else {
        return false;
    }
}

int main() {
    int c = 0;
    vector<int> v;
    for (int i = 000001; i <= 999999; i++) { 
        v.push_back(i);
        if (summ_6(v, 0, 0)) {
            c++;
        }
    }
    cout << c;
    
    return 0;
}

Answer 1

Вот пример решения, но тут не учитывается 000000 билет. Вообще проверять не обязательно начинать с 1, так как все числа до 1001 точно не будут удовлетворять заданию - там слева будет ноль, а справа не ноль.

#include <iostream>

using namespace std;

int sum_num(int i)
{
    int sum=0;
    while(i)
    {
        sum+=i%10;
        i = int(i/10);
    }
    return sum;
}

bool check_ticket(int i)
{
    int left_part, right_part;
    left_part=int(i/1000);
    right_part=i-left_part*1000;
    if(sum_num(left_part)==sum_num(right_part)) return true; else return false;
}

int main() {
    int c = 0;
    for (int i = 1001; i <= 999999; i++) {
        if (check_ticket(i)) {
            c++;
        }
    }
    cout << c;

    return 0;
}

Answer 2

Через функцию, говорите...

Напишем функцию для билетов произвольной длины в произвольной системе счисления.

unsigned long long happy(unsigned int n, unsigned int base)
{
    if (n%2 || n < 2 || base < 2) throw runtime_error("Wrong data");
    auto N = [](unsigned int n, unsigned int k,
                unsigned int base, auto&&N)
    {
        if (n == 1) return (unsigned long long)(k < base);
        unsigned long long s = 0;
        for(unsigned int l = 0; l < base; ++l) s += N(n-1,k-l,base,N);
        return s;
    };
    unsigned long long s = 0;
    for(unsigned int k = 0; k <= (base-1)*n/2; ++k)
    {
        auto m = N(n/2,k,base,N);
        s += m*m;
    }
    return s;
}

Теперь, чтоб посчитать все счастливые билеты в задании, надо написать

cout << happy(6,10) << endl;

В задании имеется в виду явно не "шестизначное число", а "шестизначный билет", а билеты вполне имели номера 070115 — ну, т.е. с ведущими нулями. Так что их надо учитывать при расчетах.

Разве что мне никогда не попадался билет 000000 — с другой стороны, и шансы 1 на миллион, так что не знаю, бывает ли такой билет. Если нет — вычтите из полученного ответа 1.

Время счета для больших длин билетов, конечно, велико, надо дописать мемоизацию... но всяко меньше, чем при прямом переборе :)

P.S. Функция для сравнения сумм цифр дописывается в любое место программы и не вызывается :)

P.P.S. Вот тут набор очень интересных статей: http://www.ega-math.narod.ru/Quant/Tickets.htm

БЛОГ НА HUSL

Счастливые билеты, решить через функцию C++

Ответы (2 шт):