Имеется задача: посчитать C(n,k) в больших числах, но так, чтобы сначала производились необходимые деления, а уж потом умножения. Передумал кучу вариантов, но проблема везде одна: надо выделять массив либо из k, либо из n-k элементов (в лучшем случае битов, что тоже много), что, сами понимаете, невозможно, т.к. n и k практически не ограничены. Отсюда вопрос: как вы думаете, можно проделать необходимые операции, не прибегая к выделению массивов?
Эта тема расположена в архиве и закрыта для обсуждения.
ZOObilo: Проблема с подсчетом C(n,k)(С из n по k) в больших числах
| ZOObilo unregistered Автор темы |
| Harkonnen Member 1602/1825 ответов 25 лет на iXBT, с февраля 2000 Чаще пишет в "Наука" (45%) | ZOObilo 1. Почему важен процесс, а не результат? Это я о делениях, там сложений достаточно. 2. Как без массивов планируется получить результат если он может содержать кучу цифр? |
| ZOObilo unregistered Автор темы | 1. Ну, сказано: сделать так. И все (ну задача в универе...) 2. Ясно, что для хранения больших чисел будет использоваться массив. Но это, в принципе, не наше дело. Можно даже представить, что это не я писал, а внешняя dll-ка. Суть в том, чтобы не использовать массив, где количество элементов будет большим числом. |
| Softwarer Member | ZOObilo: Хм. Имхо направление довольно очевидно. Насколько мне изменяет память, если сократить k! в числителе и знаменателе, C(n,k)=n*(n-1)*...*(n-k+1)/(n-k)!. Осталось сократить получившуюся дробь. На практике, полагаю, вполне хватит пробежать по знаменателю, сокращая его множители с кратными из числителя. В принципе же, нужно сокращать каждый множитель из знаменателя на НКО с очередным элементом из числителя, пока не сократишь весь знаменатель (сократится по определению, то есть за выход из цикла здесь можно не волноваться). Останется лишь перемножить оставшееся в числителе.Имеется задача: посчитать C(n,k) в больших числах, но так, чтобы сначала производились необходимые деления, а уж потом умножения. Передумал кучу вариантов, но проблема везде одна: надо выделять массив либо из k, либо из n-k элементов (в лучшем случае битов, что тоже много), что, сами понимаете, невозможно, т.к. n и k практически не ограничены. Отсюда вопрос: как вы думаете, можно проделать необходимые операции, не прибегая к выделению массивов? |
| ZOObilo unregistered Автор темы | Это то понятно. Только вот как это сделать, не храня массив, а? |
| Softwarer Member | ZOObilo: Хм. Достаточно просто. Суть в том, что тебе все время надо помнить, какие операции осталось выполнить, храня эти операции в виде диапазона n1..n2. Примерно так:Это то понятно. Только вот как это сделать, не храня массив, а? |
| ZOObilo unregistered Автор темы | Все еще проще. Пробегаем по i от 1 до k и СНАЧАЛА умножаем текущий результат на n - k + i, а потом делим на i. А делиться будет потому, что когда мы делим на i у нас в произведении есть уже i подряд идущих чисел, одно из которых заведомо делится на i. Вот и все. Всем спасибо за советы...  |
Если Вы считаете это сообщение ценным для дискуссии (не обязательно с ним соглашаться), Вы можете поблагодарить его автора, а также перечислить ему на счет некоторую сумму со своего баланса (при отзыве благодарности перечисленная сумма не будет вам возвращена).
Также вы можете оценить сообщение как неудачное.
В течение суток можно 20 раз оценить сообщения разных участников (купите Premium-аккаунт, либо оплачивайте оценки сверх лимита).
Эта тема расположена в архиве и закрыта для обсуждения.
Последние обсуждения в Конференции
Последние темы без ответов
| сегодня | Как от вас отписаться OС и сист. ПО |
| вчера | Наушники для E-MU Tracker Pre. Цифр.звук |
| вчера | Ведьмак 3 на объектах алиасинг Игры |
| вчера | Помогите разобрать монитор Asus VG23AH Мониторы |
| вчера | Нужно найти бюджетную замену давно ушедшему Сабу Inspire 5100 Стерео |
| 2 дня | Ми Исп: чудесное совпадение - сегодня День Рождение. 🎂 Флуд |
| 2 дня | AirPods 4 ANC для игр? Цифр.звук |
20+ лет назад в этот день обсуждали
| 2001 | Есть один вопрос Цифр.звук |
| 2001 | Чем стереть содержимое УФПЗУ? Память |
| 2002 | "Прокси" для почты? ;) Посоветуйте... Сети |
| 2002 | DRIVER_IRQL .... ХР летит в синий єкран OС и сист. ПО |
| 2002 | Помогите с include ($переменная) Интернет |
| 2002 | Новые ЗОЛОТЫЕ игры! Игры |
| 2002 | Проблемы после конвертирования MPEG-1 в DIVx Видеозахват |
| 2002 | . Господа кто пользовался услугами e-bay???ПОМОГИТЕ!!! Тех. поддержка |
| 2002 | Отломал отвёрткой 3 єлемента от SL75DRV2, но она работает. Чем грозит? Сист. платы |
| 2005 | Новые модели с Overdrive-ом на MVA\PVA матрицах. Мониторы |