Общая идея асимметричного шифрования

Представим, что Алиса и Боб живут в стране, в которой вся почтовая система абсолютно аморальна и почтовые служащие читают всю незащищенную корреспонденцию. Могут ли Алиса и Боб обмениваться сообщениями конфиденциально? Вообще говоря, это технически возможно [7]:

1. Алиса кладет свое письмо в железный ящик и, заперев его на замок, отправляет Бобу.

2. Боб при получении ящика, (внимание!) берет свой замок и, дополнительно заперев им ящик, отправляет обратно.

3. Алисе ящик приходит уже с двумя замками (напомню с первым замком Алисы, от которого у нее есть ключ, и со вторым — Боба, от которого ключ есть только у Боба).

4. Алиса снимает свой замок, и отправляет ящик обратно Бобу

5. Бобу приходит ящик с уже одним его замком, от которого у него есть ключ

6. Боб отпирает оставшийся его замок своим ключом, и читает сообщение.

К сожалению, все имеющиеся алгоритмы до сих пор требуют снятия шифров в той очереди, в которой они были применены. Однако систему шифрования с открытыми ключами можно создать, если использовать односторонние функции.

Что такое односторонняя функция? К примеру есть функция удвоение, т.е удвоить(4)=8, она двухсторонняя, т.к. из результата 8 легко получить исходное значение 4. Односторонняя функция — та функция после применения которой практически невозможно получить исходное значение. К примеру, смешивание желтой и синей краски — пример односторонней функции. Смешать их легко, а вот получить обратно исходные компоненты — невозможно. Одна из таких функций в математике — вычисление по модулю.

Алгоритм Диффи-Хеллмана

За основу алгоритма Хеллман предложил функцию Y^x (mod P) – получение остатка от деления Y^xна P. Обратное преобразование для такой функции очень сложно, и можно сказать что, по сути, заключается в полном переборе исходных значений.

К примеру вам сказали, что 5^x (mod 7) = 2, попробуйте найдите x? Нашли? А теперь представьте что за Y и P взяты числа порядка 10³⁰⁰.

Проиллюстрируем применение алгоритма Диффи-Хеллмана следующим примером [7]

	Алиса	Боб
Этап 1	Оба участника договариваются о значениях Y и P для общей односторонней функции. Эта информация не является секретной. Допустим, были выбраны значения 7 и 11. Общая функция будет выглядеть следующим образом: 7x (mod 11)
Этап 2	Алиса выбирает случайное число, например 3, хранит его в секрете, обозначим его как число A	Боб выбирает случайное число, например 6, хранит его в секрете, обозначим его как число B
Этап 3	Алиса подставляет число A в общую функцию и вычисляет результат 73 (mod 11) = 343 (mod 11) = 2, обозначает результат этого вычисления как число a	Боб подставляет число B в общую функцию и вычисляет результат 76 (mod 11) = 117649 (mod 11) = 4, обозначает результат этого вычисления как число b
Этап 4	Алиса передает число a Бобу	Боб передает число b Алисе
Этап 5	Алиса получает b от Боба, и вычисляет значение bA (mod 11) = 43 (mod 11) = 64 (mod 11) = 9	Боб получает a от Алисы, и вычисляет значение aB (mod 11) = 26 (mod 11) = 64 (mod 11) = 9
Этап 6	Оба участника в итоге получили число 9. Это и будет являться ключом.

 

 

Стеганография

 

Куайны и эзотерические языки

Задача №312.  Программа печатает саму себя

Идея самовоспроизводящихся автоматов зародилась на заре компьютерной эры, если не раньше. Упоминания об этом встречаются в работах Джона фон Неймана.

Программы, выводящие свой собственный код, называются куайны (Quine)[43].Написать куайн на C++, не используя сохранение в файл, строковый поток и другие ухищрения.

Решение

Существует достаточно известное решение этой задачи на языке C

#include <cstdio>

main(){

char *a = "main(){char *a = %c%s%c; int b = '%c'; printf(a,b,a,b,b);}";

int b = '"';

printf(a,b,a,b,b);

}

Здесь код выводится без заголовочных файлов. Попробуем улучшить решение

#include<cstdio>

char *program = "#include <cstdio>%cchar *program = %c%s%c;%cint main(){%cprintf(program, 10, 34, program, 34, 10, 10, 10, 10, 10, 10);%c return 0;%c}%c";

int main(){

   printf(program, 10, 34, program, 34, 10, 10, 10, 10, 10, 10);

   return 0;

}

Поначалу написание куайна кажется чем-то сродни черной магии, а его код – набором символов без всякого видимого смысла.Однако это не так. Создание куайна является сложной алгоритмической задачей, требующей знания синтаксиса, грамматики и работы со строками. Рассмотрим общие принципы создания куайнов.

Возьмём инструкцию языка для вывода и передадим ей как параметр код программы. Однако в коде мы снова используем этот же код и так далее — возникает бесконечная рекурсия. Но что можно сделать для того, чтобы не передавать строковую константу? Решение — поместить строку (копию части кода) в переменную. Для удобства назовём такую строку s-строкой, а переменную с этой строкой — s-переменной. Чтобы и в s-переменной не было рекурсии, мы просто исключим из неё фрагмент со значением этой самой переменной. Например, на языке Cэто может выглядеть так:

char s[]="char s[]=;";

Далее, при выводе, мы подставим значение s-строки в её же определение в коде (в примере выше — перед тремя последними символами). Здесь же возникает ещё несколько проблем. Первая проблема — при подстановке в s-строке нельзя использовать символы, которые поведут себя в коде не так, как надо. Например, мы не можем так просто вставить кавычку — ведь вместо того, чтобы стать частью s-строки, она завершит её определение, и выводимый код не будет совпадать с исходным, являясь некорректным вообще.

Можно использовать другой вариант кавычек — так, во многих языках разрешено использование как одинарных, так и двойных кавычек для задания строки, а отличие состоит в том, что можно без проблем использовать одну кавычку в константе, если она ограничивается другими. То есть, код ' " ' создаст односимвольную строку с двойной кавычкой, а код " ' " — с одиночной. Если использовать этот вариант, удобно вначале задать переменную с какой-либо кавычкой, а затем использовать её при выводе.

Следующая проблема — вставка другой строки (или символа с каким-либо кодом) в вывод s-строки. Решение здесь очевидно — брать подстроку s-строки специальной функцией, выводить её, далее выводить то, что надо вставить, затем выводить другую подстроку s-строки. [7]

Попробуем описать более сложный куайн на C++.

Iэтап. S-строку зададим как текст, состоящий из одной кавычки. Также опишем функцию rec() с тремя аргументами – строкой 1, символом и строкой 2. Эта функция будет заменять в строке 1 символ (escape-последовательность) строкой 2 – фактически строкой, которая выводит escape-последовательность как текст. Если s-строка будет включать код программы, то z-строка содержит то же самое, но с escape-последовательностями, замененными обычным текстом.

#include<iostream>

usingnamespacestd;

strings="\"";

voidrec(string&s, char c, string str){

size_t p=0;

while((p=s.find(c,p))!=string::npos){

   s=s.substr(0,p)+str+s.substr(p+1);p+=str.length();

}

}

int main(){

string z=s;

rec(z,’\\’,"\\\\");rec(z,’\n’,"\\n");rec(z,’"',"\\\"");

cout<<"#include <iostream>\nusing namespace std;\nstring s=\""<<z<<s;

}

IIэтап. Сформируем s-строку следующим образом: скопируем в неё весь код программы, начиная от voidrec… до конца программы. Затем внутри s-строки заменим каждый символ \ (backslash) на \\, каждый символ “ (двойная кавычка) на \”, а каждый перевод строки на \n.

Окончательный код будет выглядеть так:

#include <iostream>

using namespace std;

string s="\";\nvoid rec(string& s, char c, string str){\n size_t p=0;\n while((p=s.find(c,p))!=string::npos){\n   s = s.substr(0,p) + str + s.substr(p+1);p+=str.length();\n }\n}\nint main(){\n string z=s;\n rec(z,’\\\\’,\"\\\\\\\\\"); rec(z,’\\n’,\"\\\\n\");rec(z,’\"',\"\\\\\\\"\");\n cout<<\"#include <iostream>\\nusing namespace std;\\nstring s=\\\"\"<<z<<s;\n}";

void rec(string& s, char c, string str){

size_t p=0;

while((p=s.find(c,p))!=string::npos){

   s = s.substr(0,p) + str + s.substr(p+1);p+=str.length();

}

}

int main(){

string z=s;

rec(z,'\\',"\\\\"); rec(z,'\n',"\\n"); rec(z,'"',"\\\"");

cout<<"#include <iostream>\nusing namespace std;\nstring s=\""<<z<<s;

}

Семантические сети

 

Нейронные сети

 

Список задач книги

Задача №1. Сумма чисел в файле. 21

Задача №2. Два бандита. 23

Задача №3. Метро. 24

Задача №4. Счастливый турист. 24

Задача №5. Арифметическая прогрессия. 25

Задача №6. Обмен без третьего. 26

Задача №7. Бросание тела под углом к горизонту. 27

Задача №8. Закон Амдала. 27

Задача №9. Среднее число. 27

Задача №10. Зарплата. 28

Задача №11. Золотой песок (acmp.ru) 29

Задача №12. Маршрутки. 33

Задача №13. Коробки. 34

Задача №14. Сломанные часы.. 35

Задача №15. Принц и дракон. 36

Задача №16. ГТС.. 39

Задача №17. Холодильник. 39

Задача №18. Коды Хемминга 7-4. 42

Задача №19. День программиста (acmp.ru) 42

Задача №20. Шахматная задача. 43

Задача №21. Один в поле воин. 44

Задача №22. Зернышки. 46

Задача №23. Обмен. 50

Задача №24. Старояпонский календарь. 50

Задача №25. Возраст. 51

Задача №26. Баскетбол. 55

Задача №27. Монетки. 56

Задача №28. Прямоугольник с наименьшей площадью.. 57

Задача №29. Пиратская добыча. 58

Задача №30. Перепись. 59

Задача №31. Big и littleendian. 60

Задача №32. Раскраска таблицы умножения. 60

Задача №33. Числа Фибоначчи. 62

Задача №34. Снова Фибоначчи (acmp.ru) 62

Задача №35. Бит-реверс (acmp.ru) 63

Задача №36. Ребус КТО+КОТ=ТОК.. 64

Задача №37. Гуси и кролики. 65

Задача №38. Подарки Деда Мороза. 66

Задача №39. Тест простоты.. 66

Задача №40. Количество простых. 68

Задача №41. Космические захватчики (e-olymp) 69

Задача №42. Роботы.. 71

Задача №43. Оттепель. 72

Задача №44. Лентяй. 73

Задача №45. Нули в двоичной записи. 74

Задача №46. Побитовый вывод числа. 75

Задача №47. Битые яйца (старинная задача) 75

Задача №48. Калькулятор +1 ×2. 76

Задача №49. Цифровой корень. 76

Задача №50. Лиса Алиса и кот Базилио (acmp.ru) 77

Задача №51. НОД (алгоритм Евклида) 78

Задача №52. Возрастающий подмассив. 79

Задача №53. Шестерёнки. 80

Задача №54. Игра «Угадай число». 80

Задача №55. Таймер (acmp.ru) 81

Задача №56. Замечательные числа. 82

Задача №57. Рассадка гостей. 84

Задача №58. Замок (acmp.ru) 85

Задача №59. Бинарные числа (acmp.ru) 86

Задача №60. Садовник (e-olymp) 87

Задача №61. Кубы 888. 88

Задача №62. Указатель на указатель. 95

Задача №63. Машинный эпсилон. 96

Задача №64. Подмассив массива. 98

Задача №65. Типовая задача с массивом.. 99

Задача №66. Сдвиг перестановки. 100

Задача №67. NEERC (acmp.ru) 101

Задача №68. Равномерное распределение. 103

Задача №69. Разворот. 103

Задача №70. Изношенная клавиатура. 104

Задача №71. Светофорчики. 105

Задача №72. Произведение цифр (acmp.ru) 106

Задача №73. Нечётно повторяемый. 107

Задача №74. Статистика (acmp.ru) 108

Задача №75. Поле чудес (acmp.ru) 109

Задача №76. Билетики (acmp.ru) 110

Задача №77. Решето Эратосфена. 112

Задача №78. Робот-погрузчик. 113

Задача №79. Спутник «Фотон» (ЕГЭ С4 №27) 114

Задача №80. Пилообразная последовательность (acmp.ru) 116

Задача №81. Города и радиостанции (acmp.ru) 118

Задача №82. Максимальная тройка (acmp.ru) 119

Задача №83. Поиск прямоугольников (acmp.ru) 120

Задача №84. Замена повторяющихся. 124

Задача №85. Выборы жрецов (acmp.ru) 125

Задача №86. Автотрасса. 128

Задача №87. Мегасортировка. 129

Задача №88. Арифметическая прогрессия – 2 (acmp.ru) 131

Задача №89. Минимальная сумма (e-olimp) 132

Задача №90. Аудитории. 133

Задача №91. Музей (acmp.ru) 135

Задача №92. Диагонали. 138

Задача №93. MaxMin и MinMax. 139

Задача №94. Проверка на симпатичность (acmp.ru) 140

Задача №95. Табло. 142

Задача №96. Морской бой. 144

Задача №97. Седловые точки (acmp.ru) 145

Задача №98. Фермерское поле. 146

Задача №99. Спираль (acmp.ru) 147

Задача №100............................................................................................... Медианная фильтрация. 149

Задача №101...................................................................................................................... Minecraft 153

Задача №102............................................................................................. Случайная перестановка. 156

Задача №103.............................................................. Счастливый билет ("символьное решение") 159

Задача №104......................................................................................................... Клетки (acmp.ru) 160

Задача №105....................................................................... Искатели сокровищ (чтение из строк) 160

Задача №106......................................................................................................... Улитка на цветке. 161

Задача №107.................................................................................................... Напёрстки (acmp.ru) 162

Задача №108........................................................................................................ Детали (acmp.ru) 163

Задача №109......................................................................................... Шахматы – кони (acmp.ru) 165

Задача №110.................................................................................... Ферзь, ладья и конь (acmp.ru) 166

Задача №111............................................................................. Уравнение для 5 класса! (acmp.ru) 167

Задача №112.................................................................................................... Кругляши (acmp.ru) 168

Задача №113....................................................................................... Распаковка строки (acmp.ru) 169

Задача №114........................................................................................................... Сапер (acmp.ru) 170

Задача №115................................................................ Наименьшая система счисления (acmp.ru) 172

Задача №116................................................................................... Распознавание языка (acmp.ru) 173

Задача №117............................................................................................................. Быки и коровы.. 176

Задача №118..................................................................................................... Компьютерная игра. 177

Задача №119.................................................................................................................. Клавиатура. 178

Задача №120............................................................................................ Составить число из двух. 179

Задача №121................................................. Двойная бухгалтерия (Симферополь, 2015, II этап) 179

Задача №122........................................................................................... Годовой баланс (acmp.ru) 181

Задача №123.................................................................................................................. Палиндром.. 182

Задача №124............................................................................................. Подстроки-палиндромы.. 183

Задача №125.................................................................................................................. Телеграмма. 184

Задача №126......................................................................................................................... Скобки. 184

Задача №127.............................................................................................................. Условия Фано. 185

Задача №128........................................................................................... Степень строки (acmp.ru) 185

Задача №129.......................................................................................................... Вставить скобки. 189

Задача №130........................................................................................................................ Стрелки. 190

Задача №131............................................................................................................... Антипробелы.. 191

Задача №132.................................................................................................. ПодстрокаТуэ-Морса. 192

Задача №133......................................................................................... Поиск подстроки (acmp.ru) 194

Задача №134......................................................................................................... Налоги (acmp.ru) 197

Задача №135.......................................................................................................................... Кузнец. 199

Задача №136......................................................................................................................... Бегуны.. 202

Задача №137........................................................................................................................... Полка. 205

Задача №138................................................................................................ Игра в числа (acmp.ru) 206

Задача №139........................................................................................... Белка и бамбук (e-olymp) 208

Задача №140.......................................................................................................................... Рельсы.. 210

Задача №141.................................................................................................... Персистентный стек. 212

Задача №142........................................................................................................... Дробь (acmp.ru) 213

Задача №143........................................................................................... Камень, ножницы, бумага. 215

Задача №144................................................................................. Счастливый билет – 2 (acmp.ru) 216

Задача №145........................................................................................................................... Покер. 217

Задача №146............................................................................................................................... Сет. 220

Задача №147................................................................................. Секретное сообщение (acmp.ru) 224

Задача №148................................................................. Подстроки из одинаковых букв (acmp.ru) 225

Задача №149............................................................................... Пересечение множеств (acmp.ru) 229

Задача №150........................................................................................................................... Баллы.. 231

Задача №151.................................................................................................... Циклические сдвиги. 232

Задача №152......................................................................................................... Строки (acmp.ru) 233

Задача №153......................................................................................................................... Спамер. 234

Задача №154.................................................................................................... Экзамен по истории. 235

Задача №155................................................................................................ Jивой Jурнал (acmp.ru) 236

Задача №156........................................................................................................... Порядок байтов. 241

Задача №157....................................................................................................... Расчет маски сети. 241

Задача №158......................................................................................... Исполнитель «Удвоитель». 250

Задача №159............................................................................................ Исполнитель «Водолей». 251

Задача №160.............................................................................................. Исполнитель «Колдун». 254

Задача №161............................................................................ Исполнитель «Робот» (контейнер) 259

Задача №162......................................................................................................... Волшебная трава. 265

Задача №163....................................................................................................... Драконы (acmp.ru) 266

Задача №164.................................................................................................................. Считалочка. 267

Задача №165................................................................................................................... Робот К-79. 268

Задача №166............................................................................................................. Часы (acmp.ru) 269

Задача №167....................................................................................................... Бутылки (acmp.ru) 271

Задача №168........................................................................................... Площадьмногоугольника. 273

Задача №169................................................................................................................... Симметрия. 274

Задача №170..................................................................................................... Выпуклая оболочка. 275

Задача №171.............................................................................................. Проверка треугольника. 276

Задача №172...................................................................................................... N-угольное колесо. 277

Задача №173........................................................................................................... Две окружности. 277

Задача №174..................................................................................................... Фонарики (acmp.ru) 278

Задача №175............................................................................................................. Клад (acmp.ru) 280

Задача №176........................................................................................................................... Пицца. 282

Задача №177............................................................................................... Точка и многоугольник. 283

Задача №178................................................................................................... Точка и треугольник. 284

Задача №179....................................................................................................... Дачники (acmp.ru) 285

Задача №180....................................................................................................... Спичечная модель. 287

Задача №181.......................................................................................................... Делимость на 11. 288

Задача №182.............................................................................................. Забавная игра (acmp.ru) 289

Задача №183....................................................................................... Двоичная машина (acmp.ru) 291

Задача №184......................................................................................... Египетские знаки (acmp.ru) 293

Задача №185................................................................. Система счисления Фибоначчи (acmp.ru) 294

Задача №186..................................................................................................................... Лампочки. 296

Задача №187............................................................................... Золото племени АББА (acmp.ru) 299

Задача №188.............................................................................................................. Длинные A+B.. 301

Задача №189............................................................................................................... 2^N (acmp.ru) 301

Задача №190.................................................................................................... Длинный факториал. 302

Задача №191.................................................................................................. Очень длинное число. 304

Задача №192.................................................................................. Сумма произведений (acmp.ru) 305

Задача №193....................................................... Опупенные числа (Симферополь, II этап, 2015) 306

Задача №194........................................................................................................ Степень (acmp.ru) 314

Задача №195............................................................................................................ Подбор пароля. 316

Задача №196........................................................................................................ Ханойские башни. 317

Задача №197..................................................................................... Учебные тревоги (foxford.ru) 318

Задача №198........................................................................................................................ Монеты.. 319

Задача №199........................................................................................ Игра с числами (foxford.ru) 320

Задача №200........................................................................................................ Лесенка (acmp.ru) 320

Задача №201........................................................................................................................... Ферзи. 321

Задача №202................................................................................................... Магараджа (acmp.ru) 322

Задача №203............................................................................................. Поиск пути в лабиринте. 324

Задача №204...................................................................................................... Раскопки (acmp.ru) 325

Задача №205.................................................................................................. Анаграммы (acmp.ru) 331

Задача №206.................................................... Наименьшее и наибольшее числа из тех же цифр. 331

Задача №207...................................................................................................................... Банкомат. 332

Задача №208.................................................................................................... Сумма – 2 (acmp.ru) 333

Задача №209............................................................................................... Головоломка (acmp.ru) 334

Задача №210.......................................................................................................... Жадный фермер. 336

Задача №211...................................................................................................................... Печеньки. 337

Задача №212......................................................................................................... Дороги (acmp.ru) 339

Задача №213............................................................................................ Проверка полноты графа. 340

Задача №214............................................................................................................ Цветной дождь. 341

Задача №215............................................................................................... Граф-турнир (e-olymp) 342

Задача №216........................................................................ Острова(Симферополь, II этап, 2014) 343

Задача №217........................................................ Железная дорога (Симферополь, II этап, 2015) 344

Задача №218..................................................................................................... Вавилонская башня. 345

Задача №219................................................................................................ Заповедники (acmp.ru) 347

Задача №220...................................................................................................... Горные маршруты.. 349

Задача №221......................................................................................................... Шахматный конь. 350

Задача №222............................................................................................................. Числа Эрдёша. 353

Задача №223...................................................................................................... Табличка (acmp.ru) 353

Задача №224.......................................................................................... Игра с фишками (acmp.ru) 354

Задача №225....................................................................................................... Lines – 2 (acmp.ru) 357

Задача №226....................................................................................... Алгоритм Флойда (acmp.ru) 361

Задача №227.......................................................................................................... Флойд (e-olymp) 362

Задача №228................................................................................................ Разностные уравнения. 364

Задача №229............................................................................... Уменьшающееся число (e-olimp) 365

Задача №230...................................................... Максимальнаяподпоследовательность (acmp.ru) 366

Задача №231................................................................................................... Голодная черепашка. 367

Задача №232.................................................................... Минимальный путь в таблице (acmp.ru) 369

Задача №233...................................................................................................................... Маршрут. 370

Задача №234.............................................................................. Только вправо или вниз (acmp.ru) 372

Задача №235................................................................................ Распределение оценок (e-olymp) 373

Задача №236............................................................................... Компьютерная игра - 2 (acmp.ru) 375

Задача №237........................................................................................................ Фермер (acmp.ru) 376

Задача №238...................................................................................................................... Лестница. 377

Задача №239................................................................................................... Сломанная лестница. 378

Задача №240......................................................................................................... Заяц на лестнице. 378

Задача №241........................................................................... Лестница из кубиков (acm.timus.ru) 379

Задача №242................................................................................................ Без двух нулей подряд. 381

Задача №243....................................................................................... Волосатый бизнес (acmp.ru) 382

Задача №244........................................................................................................................... Призы.. 383

Задача №245............................................................................................................ K-ичные числа. 384

Задача №246.................................................................................... Счастливые билеты (acmp.ru) 385

Задача №247......................................................................................................... Покупка билетов. 388

Задача №248................................................................................................... Дом (Винница, 2010) 390

Задача №249.................................................................................................... Садовник-художник. 391

Задача №250.................................................................................................. Треугольник Паскаля. 392

Задача №251......................................................................................................... Салаты (acmp.ru) 393

Задача №252....................................................................................................... Шахматные ладьи. 394

Задача №253..................................................................................................... Шаблоны (acmp.ru) 396

Задача №254......................................................................................................... Нолики (acmp.ru) 397

Задача №255......................................................................................... Количество треугольников. 398

Задача №256.......................................................................................................... Флаги на мачтах. 400

Задача №257.............................................................................................. Полное число сигналов. 401

Задача №258.................................................................................. Передача сигналов по времени. 401

Задача №259..................................................................... Порождение комбинаторных объектов. 401

Задача №260........................................................................................ Две кучки камней (acmp.ru) 401

Задача №261................................................................................................... Анаграмма (acmp.ru) 403

Задача №262........................................................................................................ Имперский парад. 404

Задача №263......................................................................................... Все перестановки в строке. 405

Задача №264.................................................................................... Неподвижные точки (acmp.ru) 406

Задача №265................................................................................. Разложение числа на слагаемые. 407

Задача №266....................................................................................................................... Эскадры.. 408

Задача №267.................................................................................................................... Игра Баше. 409

Задача №268............................................................................ Антагонистические игры (acmp.ru) 409

Задача №269....................................................................................................... Игра с камушками. 411

Задача №270..................................................................................................................... Игра Ним.. 412

Задача №271.............................................. Задача ЕГЭ C3 (№26) вариант с одной кучей камней. 412

Задача №272........................................................ ЕГЭ C3 (№26) вариант с двумя кучами камней. 413

Задача №273.......................................................................................... Задача «Игра-2» (acmp.ru) 414

Задача №274.............................................................................................................. Игра «Жизнь». 415

Задача №275................................................................................. Обход шахматной доски конём.. 416

Задача №276.................................................................................. Программа печатает саму себя. 424

 

Список иллюстраций

Рис. 1 Окно выбора пакетов Cygwin. 7

Рис. 2 Установка JDK вместе с NetBeansIDE с сайта Oracle. 8

Рис. 3 Выбор компилятора, сборщика и отладчика для C++. 9

Рис. 4 Настройка конфигурации проекта. 9

Рис. 5 Передача параметров через командную строку. 17

Рис. 6. Условие с одной ветвью (блок-схема) 32

Рис. 7. Условие с двумя ветвями (блок-схема) 32

Рис. 8. Иллюстрация к задаче "Сломанные часы". 35

Рис. 9. ФункцияЕСЛИ (IF) Microsoft Office Excel. 38

Рис. 10. Иллюстрация к задаче "Холодильник". 40

Рис. 11. Неограниченная шахматная доска. 44

Рис. 12. Блок-схема оператора множественного ветвления switch в C++. 48

Рис. 13. Блок-схема цикла с параметром.. 53

Рис. 14. Иллюстрация игры к задаче "Космические захватчики". 69

Рис. 15. Циклы с условиями. 71

Рис. 16. Иллюстрация "Исполнитель садовник" (Ступеньки к информатике) 87

Рис. 17. Разложение элементарных функций в ряды Маклорена. 91

Рис. 18. Результат применения медианных фильтров к зашумленному изображению. 149

Рис. 19. Иллюстрация к задаче "Minecraft". 153

Рис. 20. Базовая таблица кодов ASCII 157

Рис. 21. Иллюстрация к задаче "Шахматы - кони". 165

Рис. 22. Иллюстрация к задаче "Ферзь, ладья и конь". 166

Рис. 23. Схема использования итераторов begin, end, rbegin, rend. 199

Рис. 24. Обработка стека. 208

Рис. 25. Иллюстрация к задаче "Рельсы". 210

Рис. 26. Иллюстрация к задаче "Камень, ножницы, бумага". 215

Рис. 27. Свойства объектов класса. 246

Рис. 28. Класс-потомок наследует свойства родительского. 248

Рис. 29. Робот R2D2 из фильма "Звездные войны". 261

Рис. 30. Псевдоскалярное (косое) произведение векторов. 273

Рис. 31. Площадь параллелограмма по трем вершинам в координатной плоскости. 273

Рис. 32. Иллюстрация к задаче "Фонарики" (acmp.ru) 279

Рис. 33. Иллюстрация к задаче "Пицца". 283

Рис. 34 Разбиение выпуклого многоугольника на треугольники. 284

Рис. 35. Проверка принадлежности точки треугольнику через площади. 285

Рис. 36 Формула Герона для вычисления площади треугольника по его сторонам.. 285

Рис. 37 Формула вычисления площади треугольника по координатам его вершин. 285

Рис. 38. Поразрядное суммирование. 300

Рис. 39. Решение задачи "Очень длинное число" в табличном процессоре. 304

Рис. 40. Пример к задаче "Головоломка". 335

Рис. 41. Иллюстрация к задаче "Игра с фишками". 355

Рис. 42 Иллюстрация к задаче "Голодная черепашка". 367

Рис. 43. Минимальный путь в таблице. 369

Рис. 44. Иллюстрация к задаче "Количество треугольников". 399

 

Список источников

 

[1]	Brian W. Kernighan, Dennis M. Ritchie.The C Programming Language. Prentice Hall PTR, Englewood Cliffs, New Jersey 07632 : AT&T Bell Laboratories, 1978. ISBN 0-13-110163-3.
[2]	Fisher, R.A., Yates, F.Statistical tables for biological, agricultural and medical research. — 3rd. London : Oliver & Boyd, 1948. ISBN 0-02-844720-4.
[3]	В., Прасолов В.Задачи по планиметрии. 4-е изд., дополненное. Москва : МЦНМО, 2001. ISBN 5-900916-82-0.
[4]	Роман Беляев. Площадь. Алголист. [В Интернете] [Цитировано: 28 Февраль 2016 r.] http://algolist.manual.ru/maths/geom/polygon/area.php.
[5]	Р. Л. Грэхем, Д. Э. Кнут, О. Паташник.Конкретная математика. Основание информатики. Москва : Мир, 1998. ISBN 5-03-001793-3.
[6]	Основы программирования на языках Си и C++ для начинающих. [В Интернете] [Цитировано: 17 Январь 2016 r.] http://cppstudio.com/.
[7]	N.J.A.Sloane. A001400 Number of partitions of n into at most 4 parts. The on-line encyclopedia of integer sequences. [ВИнтернете] The OEIS Foundation, 2016 r. [Цитировано: 10 Май 2016 r.] http://oeis.org/A001400.
[8]	Информатика. 16, Москва : Первое сентября, 2006 r.
[9]	Горьков А. Оценка сложности алгоритмов. Хабрахабр. [В Интернете] [Цитировано: 14 Январь 2016 r.] http://habrahabr.ru/post/104219/.
[10]	Структуры данных. Словари и энциклопедии на "Академике". [В Интернете] [Цитировано: 13 Январь 2016 r.] http://dic.academic.ru/dic.nsf/ruwiki/114700.
[11]	Дмитрий Амиров. Асимметричное шифрование. Как это работает? IntSystem.org Случаи из опыта разработки различных WEB проектов. Интересные факты, статьи, впечатления. Программирование и все о нем в сфере WEB. [В Интернете] InSys. [Цитировано: 22 Февраль 2016 r.] https://intsystem.org/tag/rsa/.
[12]	Александр Борзунов. Как писать квайны. Хабрахабр. [В Интернете] [Цитировано: 19 Февраль 2016 r.] https://habrahabr.ru/post/128191/.
[13]	Компиляция (программирование). Словари и энциклопедии на "Академике". [В Интернете] [Цитировано: 13 Январь 2016 r.] http://dic.academic.ru/dic.nsf/ruwiki/976938.
[14]	Самарский А.А., Михайлов А.П.Математическое моделирование: Идеи. Методы. Примеры. Москва : Физматлит, 2001.
[15]	Physical and mathematical sciences. International journal of experimental education. 2013 r., 4.
[16]	Разборов А.А. О сложности вычислений. Математическое просвещение. 1991 r., Т. 3, 3.
[17]	В.Д.Далека, А.С.Деревянко, О.Г.Кравец, Л.Е.Тимановская.Модели и структуры данных. Харьков : ХГПУ, 2000.
[18]	Вычислительная геометрия на плоскости. Е.В. Андреева, Ю.Е. Егоров. 39, Москва : Информатика, 2002 r.
[19]	Виленкин Н.Я., Шварцбурд С.И.Математический анализ. Учебное пособие для IX—X классов средних школ с математической специализацией. Москва : Просвещение, 1969.
[20]	Подбельский В. В., Фомин С. С.Программирование по на языке Си. Москва : Финансы и статистика, 2003. ISBN 5-279-02180-6.

 

 

[1] Компилятор - программа, переводящая текст программы на языке высокого уровня, в эквивалентную программу на машинном языке [2].

[2]Cygwin — это UNIX-подобная среда и интерфейс командной строки для Microsoft Windows. В системе MicrosoftWindows уже существует подобный интерфейс cmd. Вызвать командную строку можно сочетанием клавиш Win+R.

[3]GitHub — крупнейший веб-сервис для хостинга IT-проектов и их совместной разработки

[4]Дискретность - (от лат . discretus - разделенный, прерывистый), прерывность; противопоставляется непрерывности. Напр., дискретное изменение какой-либо величины во времени - изменение, происходящее через некоторые промежутки времени (скачками).

[5]Система счисления – это способ записи чисел и соответствующие ему правила действий над числами.

[6] Цифра – знак, символ для записи чисел.

[7] Согласно определению, байт – это количество бит информации, обрабатываемых процессором одновременно. В настоящее время принято считать, что байт – это 8 бит, однако в старой литературе можно встретить и другие описания байта с иным количеством бит.

[8] Иногда их называют вещественными с расширенной точностью

[9] Здесь и далее автор намеренно использует приставку «беЗ», как было принято в российской дореволюционной орфографии, считая её более верно в смысловом плане указывающей на отсутствие чего-либо

[10] Своё название метод получил от классической логической задачи: имеется два стакана, в первом из которых вино, а во втором молоко. Как добиться, чтобы в первом оказалось молоко, а во втором вино, если смешивать их нельзя? Очевидно, задача решалась с применением третьего стакана.

I->III (I - пусто,II - молоко, III - вино)

II->I (I - молоко, II - пусто, III - вино)

III->II (I - молоко, II - вино, III - пусто)

[11]Выражение, остающееся неизменным при определенном преобразовании переменных, связанных с этим выражением.

[12] такой подход в описании алгоритмов, не привязанный к конкретному языку программирования, но облегчающий понимание человеком, называется псевдокодом

[13] У этой задачи существует простое решение, известное как решение Гаусса. Известный немецкий математик Карл Фридрих Гаусс в 6 лет легко решил эту задачу, которую ему дал учитель, желая подольше занять ребенка. Гаусс заметил, что если сгруппировать числа (1+100)+(2+99)+…+(50+51), то получается 50 пар с суммой 51, в итоге 50×51=5050. Данное решение является частным случаем применения формулы суммы членов ари