Программа для нахождения C из n по k начиная с определённого порога входных данных начинает давать сбой. Где ошибка?

@ridenberg · Регистрация: 23.01.2024

Студворк — интернет-сервис помощи студентам

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
 
int factorial(int number)
{
    if (number < 0)
        return 0;
    if (number == 0)
        return 1;
    else
        return number * factorial(number - 1);
}
int main()
{
    int n, k, result;
    cout << "n = ";
    cin >> n;
    cout << "k = ";
    cin >> k;
    result = factorial(n) / factorial(k) / factorial(n - k);
    cout << result << endl;
    return result;
}

Программа выше работает стабильно, пока n не превышает 12, причём при любых допустимых значениях k (при условии, что они меньше или равны n, так работает сама формула).

Но как только я пытаюсь поставить n = 13 или выше, она почему-то начинает выдавать неправильный результат, снова не зависимо от значения k. Я не понимаю с чем это связано, помогите пожалуйста.

Математическая формула во вложении.

@vlisp · 29.01.2024, 21:08

Читай внимательно

@alexu_007 · 29.01.2024, 22:12

Сообщение от gunslinger

А зачем ООП? Для длинной арифметики?

Для длинной арифметики нет необходимости в ООП.

@gunslinger · 29.01.2024, 22:45

vlisp, читал (невнимательно), но суть уловил. Я (неожиданно) подумал про какой-то другой "особенный" способ.

alexu_007, ну это понятно (хотя предположение мое частично и логичное).

@vlisp · 30.01.2024, 13:15

Сообщение от alexu_007

Для длинной арифметики нет необходимости в ООП.

Нет необходимости в ооп вообще, однако ж его используют чтобы что?

Сообщение от gunslinger

Я (неожиданно) подумал про какой-то другой "особенный" способ.

особенность способа в том, что дроби можно сокращать и без всяких даблов (был тут такой способ)

IGPIGP · 31.01.2024, 16:26

Сообщение от vlisp

накосячтылил, но вот тут все работает
только оччччень медленннооо
прикол в том, что на питоне задачка решается вообще в 4 строчки
Добавлено через 7 минут
И еще попробуйте посчитать таким методом
...
а
Кликните здесь для просмотра всего текста
такое решает

vlisp, вы то хотите в одну строку на Python , то очень быстро. Налицо недовольство любым вариантом, кроме ООП.
В ссылке на Хабр я увидел пользу от использования симметрии биномиального треугольника. Но она не в скорости, как таковой, поскольку в цепи сложений число линий не изменяется, а лишь меняется порядок слагаемых. А в той оптимизации своего костыля, что я сейчас покажу оно пригодится, так как избавит от лишних проверок и перестановок, используя тот факт, что в левой ветви, симметрии коэффициенты, гарантировано, идут по возрастанию слева на право.
Тут предлагается снизить количество рекурсивных вызовов учитывая то, что последующий коэффициент легко получить из предыдущего: Cn-1__k = Cn_1__k-1 * (n-k-1)/k
Некоторое снижение порога переполнения тоже есть.
Но о числах сочетаний из 30 по 49 я не слыхивал. Торопились, наверное.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
unsigned long long c_n_k(long long n, long long k)
{
    if (k>n/2) k=n-k;//это полезно чтобы гарантировать C_n-1_k-1<C_n-1__k-1
    if(0==k)return 1;
    if(1==k)return n;
    if(1==n)return 0;
 
    long long C_m_p = c_n_k(n-1, k-1) ; //C из n-1 по k-1
 
    auto divideble=C_m_p/k;
 
    auto non_divideble=C_m_p%k;
 
    auto koef = (n - k) ;
 
    auto  C_m_k = koef*divideble + (koef*non_divideble)/k ;
 
    return C_m_p + C_m_k ;
}
 
int main()
{
    cout<<c_n_k(49,30)<<'\n';
    return 0;
}

Я по крайней мере, сам это сделал. Один-хря, без Хабра-хря))

@gunslinger · 31.01.2024, 17:01

Сообщение от IGPIGP

if (k>n/2) k=n-k;//это полезно чтобы гарантировать C_n-1_k-1<C_n-1__k-1

Комментарий, видимо, нужно подправить в конце (там, где сравнение происходит).

IGPIGP · 31.01.2024, 17:22

Сообщение от gunslinger

Комментарий, видимо, нужно подправить в конце (там, где сравнение происходит).

gunslinger, спасибо. Конечно, должно было быть:

C++
1
if (k>n/2) k=n-k;//это полезно чтобы гарантировать C_n-1_k-1<C_n-1__k

Думаю, модераторы пофиксят)

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

@vlisp 1071 / 992 / 153 Регистрация: 10.08.2015 Сообщений: 5,443
	29.01.2024, 21:08
	Читай внимательно 0

@gunslinger place status here 3192 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,028
	29.01.2024, 22:45
	vlisp, читал (невнимательно), но суть уловил. Я (неожиданно) подумал про какой-то другой "особенный" способ. alexu_007, ну это понятно (хотя предположение мое частично и логичное). 0