Количество сочетаний (61)

Число сочетаний - часто используемая формула в комбинаторике. Это количество вариантов выбрать из множества объектов N наборы по K объектов.

 n      n!
C  = --------
 k   (n-k)!k!

Например вычислить количество вариантов Спортлото 5 из 36

C = 36!/((36-5)! * 5!) = 376992
C = 250!/((250-110)!*110!) = 1.5120188e73 (это долго считает)

    0     1     2     3     4     5     6     7     8     9
00  П1    XY    -     FBx   Kmax  ИП1   XY    -     П0    1
10  П2    ИП2   ИП1   *     ИП0   /     П2    КИП1  FL0   11
20  ИП2   С/П   БП    00

Инструкция: k [^] n [С/П]
при индикации ошибки (ЕГГОГ) перед вводом новых данных нажать [В/О]

Регистры:
П0 - меньшее число из k и (n-k)
П1 - n - количество элементов множества
П2 - регистр накопитель результата

Программа записывает n в П1, вычисляет меньшее из k и (n-k) и записывает в П0, очищает регистр-накопитель П2, записав туда 1 (адр 00..10). Затем выполняется основной цикл вычислений (адр. 11..19) где содержимое накопителя поочерёдно умножается на число из числителя, делится на число из знаменателя, а затем декрементируются оба регистра источника данных П1 и П0. По окончании вывод резкльтатов, останов и переход к началу программы.

Программа всегда выполняет минимальное количество итераций и потому способна считать значения не доступные инженерным калькуляторам со встроенной функцией. Например пример 2 Casio fx-82MS взять не в состоянии.

Здесь файл для Калькулятор3000
http://pmk.arbinada.com/system/files/nCk.C3

File attachments: 
Прикрепленный файлРазмер
Binary Data nCk.C32.9 KB

Комментарии

Обычно программы для ПМК публиковались не только с текстом, но и с детальной инструкцией. Которая включала распределение регистров и способ запуска программы. В результате программой мог пользоваться даже пользователь, не умеющий программировать сам. Часто инструкция описывала также основные блоки программы и неочевидные приёмы, чтобы программу было легче переносить на другие ЭВМ.

Не вижу смысла порывать с этой хорошей традицией.

Иногда обстоятельства мешают. Просто пришлось срочно прерваться, вот и оставил немного не законченное сообщение. Теперь, надеюсь, Вы удовлетворены?

Мои программируемые калькуляторы:
Б3-21, Б3-34, МК-61, МК-52, МК-85
CASIO: cfx-9850GB+, fx-9750G+, fx-9750GII, fx-9860G, Algebra fx-2.0, fx-5800P, fx-7400G+
HP: 50G, 48G, 35s
TI: Nspire-CAS, Voyage-200, 89Titanium
SHARP EL-9600G

О, да. Намного лучше. Спасибо! C из n по k это полезная программа, одна из основных.

Кстати, вы не сравнивали программу с аналогичными из старых справочников (Цветкова, Трохименко, Дьяконова)?

О сравнении. Видел в одном из справочников (кажется Дьяконова) программу для Б3-34, но там факториал вычислялся трижды. Хотя, в пинципе, даже без команды Кmax можно выделить меньшее. Надо просто вычислить разность и сравнить с нулём.
Впрочем, как Вы наверное догадываетесь, для меня присутствие здесь - это скорее дань ностальгии.

Мои программируемые калькуляторы:
Б3-21, Б3-34, МК-61, МК-52, МК-85
CASIO: cfx-9850GB+, fx-9750G+, fx-9750GII, fx-9860G, Algebra fx-2.0, fx-5800P, fx-7400G+
HP: 50G, 48G, 35s
TI: Nspire-CAS, Voyage-200, 89Titanium
SHARP EL-9600G

Точность. Кстати, значительного увеличения точности (14 знаков против 12-ти) можно достичь, если не пропускать промежуточный результат через регистр, а хранить в стеке. Возможно, даже скорость повысится.

Дело в том, что команда КИП1 загружает в индикатор всегда число 0 (в МК-52 это так) и сдвигает стек вверх. Поэтому после неё пришлось бы возвращать стек в предидущее состояние, а что из команд быстрее П2 ... ИП2 или Fo - затрудняюсь ответить.

Мои программируемые калькуляторы:
Б3-21, Б3-34, МК-61, МК-52, МК-85
CASIO: cfx-9850GB+, fx-9750G+, fx-9750GII, fx-9860G, Algebra fx-2.0, fx-5800P, fx-7400G+
HP: 50G, 48G, 35s
TI: Nspire-CAS, Voyage-200, 89Titanium
SHARP EL-9600G

Ещё два знака. Пять постоянно используемых регистров стека, возможно, хранятся в более быстрой области памяти, чем тысячи регистров. Программа станет короче на три шага, сэкономится регистр. Вместо Fo можно использовать что-нибудь помельче, например XY. Быстродействие увеличится даже на старых машинках.

Но главное, конечно, это увеличение точности в 100 раз на МК-152. Когда я считал по программе C(100,10), последние две цифры в разрядную сетку не вмещались именно потому, что R2 их губил.

Таких подробностей об МК-152 я не знаю. Во первых - у меня его нет. Во вторых купить его в Украине весьма затруднительно. В третьих - зачем мне настольный калькулятор, если есть настольный компьютер. И в четвёртых - его цена. За неё можно купить штуки 3 Citizen SRP-400G или штук 7 SRP-325G. Я бы ещё понял, если бы калькулятор был переносным, с автономным питанием. Был бы он в корпусе подобном Casio cfx-9960G - тогда бы я его выбрал, причём исключительно из патриотических соображений. Хотя, если Россия выпустит ПМК в карманном исполнении и по разумной цене - буду рад и приобрету, если получится.

Мои программируемые калькуляторы:
Б3-21, Б3-34, МК-61, МК-52, МК-85
CASIO: cfx-9850GB+, fx-9750G+, fx-9750GII, fx-9860G, Algebra fx-2.0, fx-5800P, fx-7400G+
HP: 50G, 48G, 35s
TI: Nspire-CAS, Voyage-200, 89Titanium
SHARP EL-9600G

Справочники. Значит, для МК-152 придётся мне дорабатывать. Ничего страшного. Залез в справочники. У Дьяконова (даже нового) вычисляется через факториалы, оформленные как подпрограммы. Зато у Епанечникова и Цветкова («Справочник по прикладным программам для микрокалькуляторов», М.: «Финансы и статистика», 1988, стр. 48 п.1.6.7.1.) твой алгоритм, вычисления происходят в стеке, а для уменьшения числителя используется… 17.FL1 18.19 (в твоих регистрах и адресах). Для совместимости Kmax реализовано через ветвление, но результат короче твоего.

Как говорится, почувствуйте разницу. Недаром справочники Цветкова так ценились. Привожу их программу для вычисления C(n,m)=n!/(m!(n-m)!) при фиксированном m:

00.x→П1  01.↔     02.-  03.x→П0  04.FВx  05.-    06.Fx≥0  07.10   08.FВx  09.x→П0
10.1     11.П→x1  12.x  13.П→x0  14.:    15.FL1  16.17    17.FL0  18.11   19.С/П

Инструкция: m В↑ n В/0 С/П
Регистры: 0; 1 счётчики
Время вычисления — T = 2(m+2) с.
Пример. n=5, m=2, C(5,2)=10

Спасибо. Кстати, считает не только быстро, но и очень точно. Только что надо было посчитать це из ста по десять. Точными оказались не только отображаемые на экранчике МК-152, но и все 12 знаков!