Программа для нахождения 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

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

Новые блоги и статьи Все статьи Все блоги /
Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого 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) активировать флаг. . .

@vlisp 1071 / 992 / 153 Регистрация: 10.08.2015 Сообщений: 5,447
	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

Опции темы