01-basics1 (1238871), страница 2
Текст из файла (страница 2)
Наивная реализация на C это простой цикл:// возвращает n^k (m)unsigned pow_mod (unsigned n, unsigned k, unsigned m) {unsigned long long mult = n % m;unsigned long long prod = mult;while (k > 1) {prod = (prod * mult) % m;k -= 1;}return prod;}Алгоритм POWM•См.
также ℎ 4.6.3unsigned pow_mod (unsigned n, unsigned k, unsigned m) {unsigned long long mult = n % m;unsigned long long prod = 1;while (k > 0) {if ((k % 2) == 1) {prod = (prod * mult) % m; k = k - 1;}else {mult = (mult * mult) % m; k = k / 2;}}return prod;}Problem FD – разряды чисел Фибоначчи•Числа Фибоначчи растут очень быстроfib(200) == 280571172992510140037611932413038677189525•Увы, это не влезет даже в 64 бита.•Но мы можем подсчитать последний разряд числа fib(200) % 10 == 5•Последние разряды чисел фибоначчи это числа фибоначчи по модулю 101, 1, 2, 3, 5, 8, 3, 1, 4, ....•assert((8 + 3) % 10 == 1);•Задание: написать программу на C которая подсчитает последний разрядчисла fib(331), используя алгоритм F и модульную арифметикуProblem FM – вычисления по модулю m•Обобщите функцию из предыдущей задачи до функции вычисления n-гочисла Фибоначчи по любому модулю mint fib_mod(unsigned n, unsigned m);•Выведите на экран последовательности Фибоначчи по модулям 2, 3, 4,5, 6, 7, 8, 9, 10 хотя бы по 30 элементов каждой последовательности•Видите ли вы какие-нибудь закономерности?•Дополнительный вопрос: как вы обработали случай m == 0?Problem PP – периоды Пизано•В прошлой задаче были замечены некие закономерности впоследовательностях Фибоначчи по модулю m: они периодичны и новыйпериод всегда начинается с 0, 1•Напишите функцию, которая ищет длину периода по модулю m (этот периодназывается периодом Пизано) и обобщите функцию fib для гигантскихномеровint get_pisano_period(unsigned m);int fib_mod(unsigned long long n, unsigned m);•Посчитайте число 2816213588 (пожалуй в этом числе больше цифр, чемсимволов на этих слайдах) по модулю 30524Частичная оптимизация•Общая формула для периода Пизано до сих пор неизвестна.
Но подсчитанынекоторые небольшие периоды.•Скорее всего в вашем решении предыдущей задачи использоваласьредукция типа такой:unsigned fib_mod(unsigned long long n, unsigned m) {n = n % get_pisano_period(m);// ..... и так далее ....•Её можно оптимизировать, предвычислив некоторые небольшие периоды ииспользовав их как таблицу•Для этого в языке существуют массивыМассивы и мемоизацияunsigned pisanos[1000] = {0}; // означает {0, 0, 0, .... 0}int fib_mod(unsigned long long n, unsigned m) {assert (m > 0);if (m < 1000) {if (pisanos[m] == 0)pisanos[m] = get_pisano_period(m);n = n % pisanos[m];} else {n = n % get_pisano_period(m);}•Глобальный массив по умолчанию инициализирован нулями, 0 маркируетневалидное значение•Мы можем частично инициализировать массивМассивы и мемоизацияunsigned pisanos[1000] = { 0, 1, 3, 8, 6, 20, 24, 16, 12, 24,60, 10, 24, 28, 48, 40, 24, 36 };int fib_mod(unsigned long long n, unsigned m) {assert (m > 0);if (m < 1000) {if (pisanos[m] == 0)pisanos[m] = get_pisano_period(m);n = n % pisanos[m];} else {n = n % get_pisano_period(m);}•Все неинициализированные элементы всё равно нулиИнициализированность массивов•Локальный массив по умолчанию не инициализирован и считывать из негоданные это серьёзная ошибкаint foo () {int wrong[100];int corr[100] =printf ("%d\n",printf ("%d\n",arr[3] = 1;printf ("%d\n",}•{0};wrong[3]); // напечатает всё что угодноcorr[3]); // напечатает 0wrong[3]); // напечатает 1Избегайте неинициализированных массивов и неинициализированныхпеременных в своих программахProblem NS – системы счисления••Можно использовать деление с остатком, чтобы напечатать число в системе пооснованию N для небольшого N1262310= 110001010011112= 1220221123= 30110334= 4004435•В предположении, что число в системе счисления по основанию N будет иметь небольше 100 разрядов, можно использовать вспомогательный массивфиксированного размера•Напишите функциюint print_converted(unsigned n, unsigned base) {// TODO: your code here}•Которая печатает на экран число в заданной системе счисленияProblem SF – система чисел Фибоначчи•Любое положительное число единственным образом представимо как суммаФибоначчи если запретить в представлении две единицы рядом.•8 = 10000•20 = 13 + 5 + 2 = 101010•30987 = 28657 + 1597 + 610 + 89 + 34•Напишите программу которая будет печатать число типа unsigned int впредставлении Фибоначии•Возможно вы захотите мемоизировать числа Фибоначчи чтобы быстро искатьближайшее число Фибоначчи (как 28657 для 30987)= 5 + 3 = 1100= 5 + 2 + 1 = 1011https://en.wikipedia.org/wiki/Fibonacci_codinghttp://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.htmlМесть рекурсии•Рекуррентные решения могут быть довольно красивыми•Верна формула + = +1 + −1 6.108•Из неё следуют (при = и = + 1) рекуррентные соотношения2 = +1 + −1 = 2−1 + 2+1 = +1 2 + 2•Значит на каждом шаге рекурсии в зависимости от чётного или нечётного ,можно уменьшать размер задачи вдвое•Так реализован алгоритм, приведённый на следующем слайде, который неменее эффективен, чем алгоритм FАлгоритм FR// 2 = 2−1 + , 2+1 = +1 2 + 2unsigned long long fib(unsigned n) {unsigned long long fk, fkprev; unsigned k;if (n == 0) return 0ull;if (n <= 2) return 1ull;k = (n + (n % 2)) / 2; fk = fib(k); fkprev = fib(k - 1);if ((n % 2) == 0)return (2 * fkprev + fk) * fk;return fk * fk + fkprev * fkprev;}•Сравните быстродействие этого алгоритма с алгоритмом F на практикеОбсуждение•Можно ли превзойти алгоритмы F и FR?Обсуждение•Можно ли превзойти алгоритмы F и FR?•Да, и тут снова поможет математический инсайтОказывается +1•1 1=−11 0см.
1.2.8 (5)Мы ещё не проходили многомерных массивов. Но можно заметить, чтоматрица 2 × 2 это всего четыре числаProblem MF – матрицы Фибоначчи•Известно соотношение+11 1=−11 0•Задание: используйте это соотношение для быстрого вычисления чиселФибоначчи•Возможно вы захотите адаптировать алгоритм POWM для быстроговозведения в степень уже не числа, а матрицыСоблазн плавающих чисел•Вообще-то для чисел Фибоначчи легко вывести точную формулу = −, где 5=1+ 5, 2=1− 52•Почему мы изначально не пользовались ей?•Потому что плавающие числа коварны.•В языке C есть три вида плавающих чисел: float, double, long double•Также есть много операций с ними, такие как pow, sqrt, round, etc...•Давайте посмотрим возможную реализацию Фибоначчи через плавающиечислаАлгоритм FF•Наивная реализация на C для плавающих чисел двойной точности#include <math.h>unsigned long long fibd(unsigned n) {double phi = (1.0 + sqrt(5.0))/ 2.0;return round(pow(phi, n) / sqrt(5.0));}•Вычислите fibd(20), fibd(50), fibd(80)•Сравните с результатами алгоритма F•Мы обязательно займёмся плавающими числами, но позже.Домашнее задание HWF•Два игрока играют в интересную игру: изначально дано N спичек.
Первыйигрок берёт любое количество, но не все сразу спички. Теперь второй можетвзять не больше, чем вдвое больше чем первый. Далее первый берёт небольше чем вдвое больше второго. И так далее. Выигрывает тот, кто взялпоследнюю спичку (источник: 1.2.8 задача 37)•11 спичек. Первый берёт 4, второй может взять до 8 и берёт 7, победа.Запись партии: 11.4,7!•Ещё варианты: 11.3,3,5! 11.3.2.1.1.1.1.2! и т.д.•Найдите связь этой игры с числами Фибоначчи и напишите играющую в неёкомпьютерную программу•Программу после прохождения контеста высылайте на emailОписание игры и дополнительные материалы: https://en.wikipedia.org/wiki/Fibonacci_nimЛитература•С11 ISO/IEC, "Information technology – Programminglanguages – C", ISO/IEC 9899:2011•& Brian W.
Kernighan, Dennis Ritchie – The Cprogramming language, 1988• Ronald L. Graham, Donald E. Knuth, Oren Patashnik –Concrete Mathematics: A Foundation for Computer Science,1994• Donald E. Knuth – The Art of ComputerProgramming, 2011•UCSanDiegoX: ALGS200x Algorithmic Design andTechniques, EDX course.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
