Меню
Главная

Статистика

 

 


Упражнение #4.

Выбирается произвольное двузначное число и назначается первым элементом n1 последовательности псевдослучайных чисел, а затем каждый очередной элемент ni+1 получается из предыдущего элемента ni. Для этого ni возводится в квадрат, и из полученного 4-хзначного результата отбрасываются левая и правая цифры. Например: ni=25Þni=0625Þ ni+1=62. Поскольку различных чисел в такой последовательности конечное число, то, рано или поздно, она начнет самовоспроизводиться начиная с некоторого места. Поэтому алгоритм генерирует именно псевдослучайные числа. Напишите программу, генерирующую такую последовательность по заданному входному значению n1. Найдите место первого повтора ранее полученного элемента.

Вернемся к задаче об "испорченной" таблице умножения. Предположим для определенности, что вариант хранения данных оказался таким, как представленный на рис. A5-2. Учтите, что столбцы, согласно условию, "не пострадали". Как искать произведение 5´6 в "испорченной" таблице?

  1 2 3 4 5 6 7 8 9
7 7 14 21 28 35 42 49 56 63
8 8 16 24 32 40 48 56 64 72
4 4 8 12 16 20 24 28 32 36
5 5 10 15 20 25 30 35 40 45
6 6 12 18 24 30 36 42 48 54
9 9 18 27 36 45 54 63 72 81
1 1 2 3 4 5 6 7 8 9
2 2 4 6 8 10 12 14 16 18
3 3 6 9 12 15 18 21 24 27
Рис. 2.

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

Упражнение #5.

Системные оболочки Norton Commander, Far, Windows Commander предоставляют возможность, в зависимости от цели использования, менять порядок расположения имен каталогов и файлов в панелях Left и Right, выводимых ими на экран. Информация на эти панели попадает из соответствующих каталогов операционной системы. Вспомните (или выясните), как организованы каталоги, из каких записей состоят, какие поля играют роль ключей.

Что произойдет, если из второй, "испорченной" таблицы изъять столбец и строку с ключами, как на рис. A5-3? Сохранится ли возможность поиска все того же произведения 5´6?

7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
9 18 27 36 45 54 63 72 81
1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
Рис. 3.
7
8
4
5
6
9
1
2
3
Рис. 4.

Да, и более того - можно продолжить эксперименты с таблицей, и "испортить" ее настолько, что в ней вообще останется только первый столбец (рис. A5-4), но при этом возможность полного ее восстановления сохранится. Это так, поскольку соседние элементы внутри каждой строки представляют нарастающие суммы повторяющегося слагаемого (вспомните алгоритм A4-1 и рис. A4-1), причем у каждой строки ее собственное слагаемое содержится в ней - в качестве первого элемента.

Иначе говоря, мы имеем дело с зависимостью si,j+1=si,j+si,1, где i - номер строки на рис. A5-3 и A5-4, j - номер столбца на рис. A5-3, si,j - элемент таблицы на пересечении i-й строки и j-го столбца. Соотношения подобного вида принято называть рекуррентными. Применение они находят в разнообразных задачах, в том числе, связанных с обработкой таблиц. Методы и задачи, возникающие в этой связи, относят к т.н. динамическому программированию.

Назад
Недвижимость в подмосковье, рублевское шоссе коттеджи. написание курсовых по методологии. Испания продажа недвижимости в Испании, недвижимость в Испании. летом. Gta 3 iso делаю образ а он его не видит! Тесты