На планете Утипути цивилизация никак не развивалась, много тысячелетий аборигены жили в каменном веке. Пришельцы из далекой галактики готовы помочь им. Только вот общаться двум цивилизациям сложно. Даже с числами трудно разобраться: у пришельцев в инструкциях числа встречаются в разных системах счисления, а у аборигенов система счисления одна – первобытная. Это когда число изображается необходимым количеством предметов (пять палочек – это число 5). Написать алгоритм, по которому туземцы будут переводить числа из первобытной системы счисления в любую заданную. Но так как туземцы не знают цифр, они будут записывать числа «по-первобытному»: на земле начертят клеточки и будут в них выкладывать число с помощью палочек. В каждую клеточку столько палочек, каково значение цифры в данной позиции. А вместо нуля - цветочек. Таким образом, дано: гора камней (их ровно столько, каково значение числа) и горка палочек (их столько, каково основание системы счисления, в которую надо перевести «каменное» число). Например: пусть камней 28, а палочек 5. 2810=2035, значит туземцы должны для записи числа использовать 3 клеточки: в первую положить 2 палочки, во вторую – цветочек, а в третью – 3 палочки. Туземцы не умеют считать, не знают действий арифметики (не могут складывать, делить, перемножать числа, пересчитывать предметы), но они могут сравнивать числа. Для этого они выкладывают камни из одной кучки в линеечку, а под ней – камни из другой кучки, точно друг под другом; какая линеечка длиннее, то и число больше. Таким же образом они могут «скопировать» число – выложить кучку камней, изображающую число, равное данному. Алгоритм записать в виде набора инструкций и действий туземцев. Возможные действия туземцев: 1. Подойди к кучке с камнями/палочками. 2. Подойди к клеточке, помеченной красным/синим/зеленым флажком. 3. Подойди к своему соплеменнику по имени … 4. Отдай/возьми у своего соплеменника предмет. 5. Сделай шаг влево/вправо (туземец стоит теперь перед соседней клеточкой) 6. Положи предмет (камень, цветочек, палочку) или кучку предметов в клеточку (предмет кладется в ту клеточку, перед которой туземец стоит). 7. Пометь клеточку (в землю рядом с клеточкой втыкается флажок). 8. Вытащи флажок, которым помечена клеточка. 9. Возьми предмет из кучки/клеточки. 10. Положи предмет в кучку. 11. Ответь на вопрос «есть ли в кучке/клеточке предметы». Виды инструкций в алгоритме: 1. Действия туземца. Вы можете использовать нескольких туземцев (назовите их AА, BB, CC). Перед действием указывайте, к кому из туземцев обращаетесь. 2. Если <ответ да> выполни действие. 3. Пока <ответ да> выполняй до слов «закончить пока». Перечисляются действия «закончить пока».
Теория алгоритмов
У этой задачи пока нет материалов