Программа на C, решающая уравнение в натуральных числах

[Ktina]

Пытаюсь написать на C программу, получающую на входе натуральное число $Y$ и решающую в натуральных числах уравнение

$$n+S(n)+S(S(n))+ \dots +\underbrace{S(S(\dots S}_{n-1}(n)))=Y$$

Код получился вот такой:

Используется синтаксис C

#include <stdio.h>

#include <conio.h>

int SumDigits ( int N)

{

int d, sum = 0;

while ( N != 0 )

{

d = N % 10;

sum = sum + d;

N = N / 10;

}

return sum;

}

void main()

{

int Y, N, M, s, i, j, k, a;

a = 0;

printf ( "\n Enter a number ");

scanf ( "%d", &Y);
for (i = 1; i <= Y; i++) {
    s = i;
    M = i;
for (j = 1; j <= i-1; j++) {
s = SumDigits(s);
M+=s;
}
if (M == Y) {
    printf ( "%d\n", i);
    a++;

}


}

if(a == 0) printf ("No solutions");


getch();

}

 

Пожалуйста, помогите хотя бы протестировать эту программу. Укажите на ошибки.
Заранее благодарю!

[_Ivana]

Если S - неубывающая функция, то решается тривиально методом дихотомии, если определить границы диапазона единственного корня. Если нет - в общем случае корней бесконечное количество. Все зависит от функции S.

[Ktina]

_Ivana
$S$ - это сумма цифр.

[FomaNeverov]

Как должна работать эта программа? То есть, если на вход подать "12345", то должно быть 12345 + 15 + 6 = 12366?

[FomaNeverov]

Ktina, запустил я вашу программу, в моём варианте она выглядит так:

int SumDigits(int N)
{
    int d, sum = 0;

    while(N != 0)
    {
        d = N % 10;
        sum = sum + d;
        N = N / 10;
    }

return sum;
}


void Widget::press_pbtn_01()
{

    QMessageBox msgBox;
    QString str;

    int Y, N, M, s, i, j, k, a;

    a = 0;
    k = 0;
    Y = 12345;

    for (i = 1; i <= Y; i++)
    {
        s = i;
        M = i;

        for (j = 1; j <= i-1; j++)
        {
            s = SumDigits(s);
            M += s;

            k++;
        }

        if (M == Y)
        {
            //printf ( "%d\n", i);
            msgBox.setText(QString::number(i));
            msgBox.exec();

            a++;
        }
    }


    str = fn_SpsToInt(QString::number(M));
    ui->label_01->setText("M = " + str);

    str = fn_SpsToInt(QString::number(k));
    ui->label_02->setText("k = " + str);
}

Результат работы программы для входного числа 12345:



M - это переменная М, в которой (очевидно) накапливается результат
k - это счетчик, количество вызовов функции s = SumDigits(s);

Это тот результат, который вы хотели получить? При этом условие if (M == Y) не было выполнено ни разу, поэтому в вашем консольном варианте вы бы не получили никакого вывода на экран.

[Ktina]

FomaNeverov в сообщении #1325589 писал(а):

Как должна работать эта программа? То есть, если на вход подать "12345", то должно быть 12345 + 15 + 6 = 12366?

Не так.
Допустим, я хочу решить уравнение:

$$n+S(n)+S(S(n))+ \dots +\underbrace{S(S(\dots S}_{n-1}(n)))=2000000$$

Программа получает на входе 2000000 и выдаёт, что решений нет (там же остаток 2 при делении на 3 ).

[FomaNeverov]

При чём тут остаток 2 при делении на 3? У вас условие - if (M == Y). Y - это ваше входное число 2 000 000. М - это ваш аккумулятор суммы. Программа выдаст единственное решение, когда сумма будет равна введённому числу. Но вы ведь к М не по единице прибавляете? Легко может перескочить - зачем считать дальше?

И взяли бы уж для начала число поскромнее, у меня при 12345 считает пару секунд, возможно при 2 млн будет считать недели или годы, а вы будете ждать результата...

И вообще, для проверки правильности алгоритма желательно прогнать его через маленькие значения, которые можно проверить карандашиком. Если при Y = 10 даёт правильный ответ и при Y = 11 тоже - скорее всего алгоритм правильный.

[_Ivana]

FomaNeverov в сообщении #1325660 писал(а):

у меня при 12345 считает пару секунд

И эти люди говорят, что Питон медленнее их запорожца...

[Dmitriy40]

Приведу значения левой части для $n=1\ldots1000$ (отсортировано по возрастанию и удалены дубли) для проверки какие $Y$ имеют решения:

Используется синтаксис Text

1 4 9 16 19 25 31 36 45 46 49 58 61 64 79 81 82 94 99
100 106 117 118 121 133 136 145 148 151 154 162 171 172 175 187 190 193 196 198 199
202 225 226 229 234 241 244 250 256 261 262 265 270 280 283 288 295 298
301 306 307 316 328 334 337 340 342 351 352 358 364 370 378 385 388 391
405 409 412 414 418 424 430 441 442 445 460 466 469 472 475 477 478 481 486 496 499
511 514 520 522 526 531 532 549 550 553 556 558 568 574 580 594 598
601 604 612 619 621 622 630 631 634 640 646 658 661 666 673 675 676 688 694
700 702 706 711 712 715 727 729 730 738 742 745 748 769 774 778 781 784 790 792 796
801 802 820 823 835 837 838 841 850 855 856 874 877 880 882 883 891 892 898
910 913 918 925 928 931 952 954 955 958 964 970 981 982 985 990
1000 1006 1012 1018 1026 1036 1039 1044 1051 1054 1057 1060 1062 1066 1071 1072 1090 1093 1096 1098
1108 1114 1116 1117 1120 1129 1134 1144 1147 1150 1161 1162 1168 1170 1179 1180 1183 1195 1197 1198
1201 1210 1213 1216 1228 1234 1240 1242 1251 1252 1255 1267 1270 1273 1278 1279 1282 1285 1288
1305 1309 1314 1321 1324 1330 1336 1341 1342 1350 1354 1360 1363 1368 1375 1378 1386 1390 1396
1414 1417 1420 1422 1426 1431 1432 1438 1441 1450 1453 1458 1465 1468 1480 1485 1492 1494 1498
1501 1504 1507 1521 1522 1525 1530 1540 1546 1548 1552 1558 1566 1570 1576 1579 1594
1600 1606 1611 1612 1630 1633 1638 1645 1648 1654 1660 1674 1684 1687 1690 1693
1701 1702 1705 1708 1710 1720 1723 1735 1738 1746 1750 1756 1762 1774 1777 1780 1782 1791 1792
1804 1807 1809 1810 1818 1822 1825 1828 1846 1849 1854 1861 1864 1870 1872 1876 1882 1890
1900 1903 1915 1918 1921 1926 1927 1930 1935 1936 1954 1957 1960 1971 1972 1978 1980 1990 1993 1996 1998 1999
2007 2008 2020 2032 2034 2047 2050 2061 2070 2074 2086 2089 2095
2101 2106 2115 2119 2140 2142 2146 2151 2170 2173 2178 2185 2194
2200 2214 2218 2227 2230 2241 2248 2250 2251 2263 2275 2286 2290
2302 2304 2317 2320 2331 2332 2344 2356 2362 2365 2367 2371 2376 2398
2401 2403 2410 2416 2421 2422 2425 2430 2439 2443 2455 2466 2470 2497
2502 2503 2509 2511 2518 2533 2538 2545 2560 2565 2569 2572 2574 2584 2587 2590
2601 2610 2614 2626 2628 2635 2641 2646 2665 2668 2680 2691 2695
2713 2725 2727 2734 2737 2740 2754 2763 2767 2770 2788 2790 2794 2799
2803 2808 2815 2818 2826 2830 2842 2857 2860 2862 2866 2871 2880 2884 2896 2898 2899
2905 2911 2934 2938 2950 2959 2965 2970 2980 2992 2995
3004 3006 3010 3040 3051 3058 3061 3069 3082 3085 3087
3112 3123 3130 3132 3141 3142 3154 3159 3166 3175 3195
3217 3220 3222 3231 3232 3258 3265 3274 3289 3294
3310 3313 3321 3328 3330 3355 3361 3366 3382 3384 3394
3409 3411 3433 3436 3447 3454 3475 3483 3490 3499
3501 3514 3519 3535 3544 3555 3556 3564 3580 3586 3591
3607 3618 3625 3628 3636 3652 3654 3658 3670 3690 3699
3706 3709 3715 3726 3730 3760 3762 3771 3780 3790
3802 3805 3807 3814 3825 3843 3859 3868 3870 3871 3874 3879 3888
3904 3915 3922 3946 3949 3951 3952 3960 3976 3987 3994
4009 4014 4030 4041 4042 4075 4077 4081 4084 4120 4123 4131 4140 4147 4153 4165 4194
4201 4204 4210 4221 4234 4246 4255 4266 4285 4300 4306 4309 4311 4329 4354 4366 4378 4392 4399
4401 4408 4444 4447 4450 4455 4462 4489 4491 4516 4518 4519 4522 4525 4570 4581 4590 4594
4600 4615 4624 4644 4660 4666 4680 4681 4687 4705 4707 4738 4741 4759 4762 4770 4795
4801 4804 4833 4840 4849 4852 4860 4873 4894 4905 4933 4939 4948 4950 4954 4959 4984
5002 5014 5022 5026 5031 5056 5085 5095 5098 5110 5121 5148 5164 5170 5176
5211 5227 5242 5257 5274 5281 5301 5314 5335 5337 5338 5386 5389 5391
5400 5410 5434 5458 5463 5488 5490 5491 5530 5535 5542 5572 5580 5593 5596 5598
5650 5652 5662 5670 5674 5704 5715 5743 5746 5760 5767 5778
5818 5821 5824 5841 5850 5875 5890 5904 5905 5929 5940 5962 5967 5983 5986
6021 6030 6034 6067 6093 6106 6111 6148 6165 6178 6201 6228 6229 6250 6291 6301 6322 6345 6382 6390
6403 6408 6466 6471 6472 6480 6534 6538 6553 6570 6597 6610 6634 6660 6682 6715 6723 6750 6754 6795 6796
6826 6840 6858 6877 6898 6921 6930 6958 6970 6984 7011 7039 7042 7101 7120 7123 7191 7192 7195
7258 7282 7290 7330 7363 7380 7402 7444 7470 7474 7525 7546 7560
7606 7618 7650 7687 7690 7740 7762 7768 7830 7843 7849 7915 7920 7930 7987
8001 8011 8091 8101 8173 8190 8254 8280 8335 8370 8416 8460 8497
8550 8578 8640 8659 8730 8740 8820 8821 8910 8911 8991 8992
9090 9180 9270 9360 9450 9540 9630 9720 9810 9900 9999

[Ktina]

Dmitriy40
Большое спасибо!

[FomaNeverov]

Ktina в сообщении #1325698 писал(а):

Dmitriy40
Большое спасибо!

Ну, и это всё - получили готовый результат и успокоились? А почему не работает ваш код на Си - вас не интересует?

[guryev]

Ktina в сообщении #1325544 писал(а):

Пытаюсь написать на C программу, получающую на входе натуральное число $Y$ и решающую в натуральных числах уравнение

$$n+S(n)+S(S(n))+ \dots +\underbrace{S(S(\dots S}_{n-1}(n)))=Y$$

Код получился вот такой:

Код вполне рабочий, хотя можно было бы сократить трудоёмкость с ${\textit{O}}(Y^2)$ до ${\textit{O}}(Y{\rm ln}Y)$, а также уменьшить раза в два количество проходов внешнего цикла. С этими изменениями и $Y=200000000$ решается за вполне разумное время, а так - долго, конечно...

[Ktina]

FomaNeverov в сообщении #1326297 писал(а):

Ну, и это всё - получили готовый результат и успокоились? А почему не работает ваш код на Си - вас не интересует?

В русском языке нет аналога арабскому слову بلى , означающему "да", но употребляющемуся только в ответ на отрицание. Одна моя знакомая израильская арабка, получившая высшее медицинское образование в СССР, предложила перевести это слово на русский так: "да нет". В некоторых случаях этот перевод годится. Так вот, отвечаю Вам: да нет, интересует, и ещё как!

-- 12.07.2018, 22:41 --

guryev в сообщении #1326327 писал(а):

Код вполне рабочий, хотя можно было бы сократить трудоёмкость с ${\textit{O}}(Y^2)$ до ${\textit{O}}(Y{\rm ln}Y)$, а также уменьшить раза в два количество проходов внешнего цикла.

А не подскажете, как именно?

[guryev]

guryev в сообщении #1326327 писал(а):

... сократить трудоёмкость ... , ... уменьшить ... количество проходов внешнего цикла.

Ktina в сообщении #1326365 писал(а):

А не подскажете, как именно?

Ну, во-первых, нетрудно заметить, что значение ${S(S(\dots (n)))$ после крохотного количества итераций становится однозначным числом, и дальнейшие вызовы $S(S)$ возвращают его же. Нет нужды крутиться в цикле, прибавляя к сумме одну и ту же величину, когда есть умножение.

Кроме того, брать $Y$ в качестве верхнего предела внешнего цикла - излишество. Ясно, что наименьшее возможное значение левой части равно - чему, при любом наперёд заданном $n$?

[eugensk]

FomaNeverov в сообщении #1326297 писал(а):

Ну, и это всё - получили готовый результат и успокоились? А почему не работает ваш код на Си - вас не интересует?

Ktina в сообщении #1326365 писал(а):

интересует, и ещё как!

А что с кодом не так? Он работает и возвращает правильный результат.
Имеет смысл начинать с прямого решения, вообще без каких-либо оптимизаций, именно как у Вас.
Оптимизированная версия пишется потом, чтобы можно было её проверить сравнивая с первой
(уважаемый guryev показал совершенно правильные шаги что можно сделать, но реализуя их, и Вы, и я, неизбежно сделаем ошибки)

Потом можно сделать программу
для произвольно больших чисел
для произвольных выражений, придумать формат, и вводить формулу вместе с Y
и т.д., - но это будет другая история.