Фибоначчиева система счисления

Читайте также:

Задания II (муниципального) этапа Конкурса

По программированию и информационным технологиям

Февраля 2013 г.

Задача №1 «Система счисления с максимальной суммой цифр» (max 100 баллов)

(Автор: доцент кафедры информатики и защиты информации ВлГУ, кандидат физико-математических наук Александров Алексей Викторович)

Дано натуральное число N. Найти систему счисления с основанием k=2..16 с наибольшей суммой цифр (суммы цифр рассматривается в десятеричной арифметике) в представлении числа N. Если систем счисления с таким максимальным свойством несколько, то вывести все значения оснований с таким максимальным свойством.

Формат входных данных

Во входном текстовом файле в первой строке находится натуральное число N (N≤2³¹-1).

Формат выходных данных

На выходе программы выводится одно или несколько значений оснований (2≤K≤16), и, соответственно, сумма цифр.

Пример входного и выходного файлов

Пример входного файла	Пример выходного файла
21100	Основания 11,Сумма 11Основания 13,15,Сумма 16

Критерии оценивания задачи: каждому участнику олимпиады выдается два теста с одним небольшим (не больше ста) и одним большим числом. Тест с небольшим числом оценивается в 40 баллов, с большим числом оценивается в 60 баллов. Максимальное количество баллов 100.

Задача №2 «Фибоначчиева система счисления» (max 100 баллов)

Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т.д.

Последовательность Фибоначчи определяется следующим образом:

F1=F2=1 i>2: Fi= F i-1+F i-2,

Несколько первых её членов: 1, 1, 2, 3, 5, 8, 13, 21, 34,…

В Фибоначчиевой системе счисления участвуют все элементы последовательности, кроме первой единицы.

Эти числа ввёл в 1202 г. Леонардо Фибоначчи (Leonardo Fibonacci) (также известный как Леонардо Пизанский (Leonardo Pisano)). Однако именно благодаря математику 19 века Люка (Lucas) название "числа Фибоначчи" стало общеупотребительным.

Фибоначчиева система счисления

Теорема Цекендорфа утверждает, что любое натуральное число n можно представить единственным образом в виде суммы чисел Фибоначчи:

Число	Запись в ФСС
	0……0
F₂=1
F₃=2
F₄=3

F₅=5


F₆=8

где k1 >= k2+2, k2 >= k3+2,..., kr >= 2

Отсюда следует, что любое число можно однозначно записать в фибоначчиевой системе счисления, например:

Перевод числа в фибоначчиеву систему счисления осуществляется простым "жадным" алгоритмом: просто перебираем числа Фибоначчи от больших к меньшим и, если некоторое , то входит в запись числа , и мы отнимаем от и продолжаем поиск.

Надо написать программу для перевода натурального числа N в фибоначчиеву систему счисления.

Формат входных данных

Первая строка входного файла содержит натуральное число N (1≤N≤2³¹-1).

Формат выходных данных

Выходной файл должен содержать строку, содержащую код Фибоначчи числа N.

Пример входного и выходного файлов

Пример входных данных	Пример выходных данных
125	101011000

Задача №3 «Криптографические ключи» (max 100 баллов)

Недавно одна компания “X” разработала принципиально новый алгоритм шифрования данных, который практически невозможно взломать, но и одновременно абсолютно не ресурсоемкий. Все шифрование строится на симметричном K -ключе, то есть на числе, в двоичной записи которого ровно K единиц. Все принципиальное отличие от предыдущих алгоритмов заключалось в том, что ключ не был одним и тем же на все время соединения, а менялся после некоторых определенных интервалов времени на другой K -ключ. Также одной из особенностей разработанного алгоритма была необходимость того, чтобы каждый следующее число, соответствующее K -ключу, было больше предыдущего. Более того, специалисты компании установили, что для увеличения помехоустойчивости разница между следующим K -ключом и предыдущим K -ключом должна быть минимальна. Под разницей K -ключей понимается абсолютная разница соответствующих им чисел.

Вы работаете в этой компании, и Вам предстоит разработать алгоритм получения из исходного K -ключа следующего K -ключа в соответствии со всеми описанными выше требованиями.

Формат входных данных

В первой и единственной строке входного файла находится одно натуральное число N (1 ≤ N ≤ 10¹⁸) – соответствующий K -ключ.

Формат выходных данных

В первой и единственной строке выходного файла должно находится одно натуральное число – следующий K -ключ за соответствующим K -ключом N.

Пример входного и выходного файлов

Пример входных данных	Пример выходных данных

Критерии оценивания задачи: каждому участнику олимпиады выдается два теста с одним небольшим (не больше тысячи) и одним большим числом. Тест с небольшим числом оценивается в 40 баллов, с большим числом оценивается в 60 баллов. Максимальное количество баллов 100.

Задание №4 «Задание по процессору WORD» (max 100 баллов)

Всем участникам конкурса выдаётся Файл «Цифровая крепость.doc». Надо сделать следующие преобразования.

1. Преобразовать Файл Цифровая крепость.doc в формат html – документа.

2. Открыть преобразованный файл в редакторе Word так, чтобы были видны все теги html – документа.

3. С помощью поисковых функций редактора Word определить

Вариант	Задание
	Сколько раз в тексте встречается имя Беккер
	Сколько раз в тексте встречается имя Сьюзан
	Сколько раз в тексте встречается имя Хейл
	Сколько раз в тексте встречается имя Дэвид
	Сколько раз в тексте встречается тег – оглавления
	Сколько раз в тексте встречается слово «Интернет»
	Сколько раз в тексте встречается слово «файл»
	Сколько раз в тексте встречается слово «агент»
	Сколько раз в тексте встречается слово «взлом»
	Сколько раз в тексте встречается имя Джабб
	Сколько раз в тексте встречается слово «сэр»
	Сколько раз в тексте встречается имя Бринкерхоф
	Сколько раз в тексте встречается слово «темно»
	Сколько раз в тексте встречается слово «светло»
	Сколько раз в тексте встречается слово «такси»
	Сколько раз в тексте встречается слово «план»
	Сколько раз в тексте встречается слово «крепость»
	Сколько раз в тексте встречается слово «шифр»

Требования к выполнению: полностью выполненное задание оценивается в100 баллов.

1. Правильное преобразование файла допускает иные варианты, по сравнению с приведенным в ответах, и оценивается в 50 баллов.

2. Правильный ответ на вопрос, приведенный в вариативной части – 50 баллов.

Задание №5 «Задача по Excel» (max 100 баллов)

Всем участникам конкурса выдаётся Файл с задачами в виде таблицы «Excel_олимпиада.xls»

Требования к выполнению: четыре правильно решённые задачи по Excel суммарно оцениваются в 100баллов (1 задача – 20 баллов, 2 задача – 20 баллов, 3 задача – 30 баллов, 4 задача – 30 баллов).

Дата добавления: 2015-08-13; просмотров: 381 | Нарушение авторских прав

<== предыдущая страница	\|	следующая страница ==>
Барка Василь	\|	Черты сходства Черты отличия

mybiblioteka.su - 2015-2024 год. (0.018 сек.)