Для членов жюри Решение и тесты к заданиям II (муниципального) этапа Конкурса по программированию и информационным технологиям
27 февраля 2013 г.
Задача №1 «Система счисления с максимальной суммой цифр» (max 100 баллов)
(Автор: доцент кафедры информатики и защиты информации ВлГУ, кандидат физико-математических наук Александров Алексей Викторович)
Дано натуральное число N. Найти систему счисления с основанием k=2..16 с наибольшей суммой цифр (суммы цифр рассматривается в десятеричной арифметике) в представлении числа N. Если систем счисления с таким максимальным свойством несколько, то вывести все значения оснований с таким максимальным свойством.
Формат входных данных
Во входном текстовом файле в первой строке находится натуральное число N (N≤231-1).
Формат выходных данных
На выходе программы выводится одно или несколько значений оснований (2≤K≤16), и, соответственно, сумма цифр.
Пример входного и выходного файлов
Пример входного файла |
Пример выходного файла |
21 100 |
Основания 11,Сумма 11 Основания 13,15,Сумма 16 |
Критерии оценивания задачи №1: каждому участнику олимпиады выдается два теста с одним небольшим (не больше ста) и одним большим числом. Тест с небольшим числом оценивается в 40 баллов, с большим числом оценивается в 60 баллов. Задача оценивается max в 100 баллов.
Тесты для проверки к задаче №1:
№ варианта |
Исходные данные |
Выходные данные |
1 |
12 |
Основания 13,14,15,16; сумма 12 |
2 |
125 |
Основание 14; сумма 21 |
3 |
19 |
Основание 10; сумма 10 |
4 |
321 |
Основания 14; сумма 22 |
5 |
11 |
Основания 12,13,14,15,16; сумма 11 |
6 |
210 |
Основание 16; сумма 15 |
7 |
9 |
Основания 10,11,12,13,14,15,16; сумма 9 |
8 |
251 |
Основание 16; сумма 26 |
9 |
13 |
Основания 14,15,16; сумма 13 |
10 |
159 |
Основание 16; сумма 24 |
11 |
15 |
Основание 16; сумма 15 |
12 |
100 |
Основания 13,15; сумма 16 |
13 |
21 |
Основание 11; сумма 11 |
14 |
111 |
Основание 16; сумма 21 |
15 |
17 |
Основание 9; сумма 9 |
16 |
222 |
Основание 16; сумма 27 |
17 |
29 |
Основание 15; сумма 15 |
18 |
333 |
Основания 13,14; сумма 21 |
19 |
32 |
Основание 11; сумма 12 |
20 |
231 |
Основание 16; сумма 21 |
Код программы (Pascal)
uses
crt;
const
nmax=10000000;
var
i,v,x,m,j, maximum, summacifr, osnovanie :longint;
a:array[1..10000] of longint; c:array [2..16] of longint;
begin
clrscr; write('Vvodim chislo'); ReadLn(x); summacifr:=0; writeln('Predstavlenija');
for m:=2 to 16 do
begin
write(m); i:=0; v:=x;
While v>0 do
begin
inc(i);
a[i]:=v mod m;
v:=v div m
end; readln;
for j:=i downto 1 do
begin write (a[j]); c[m]:=c[m]+a[j]; end; writeln;
end; writeln('A teper summy cifr');
for j:=2 to 16 do
begin writeln (j,' ', c[j]); end;
ReadLn;
maximum:=c[2];
for j:=2 to 16 do
if c[j]>maximum then maximum:=c[j];
writeln('osnovaniya c mmximalnoy summoy cifr');
for j:=2 to 16 do
if c[j]=maximum then writeln(j);
readln
end.
Задача №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……0 |
F2=1 |
1 |
F3=2 |
10 |
F4=3 |
100 |
4 |
101 |
F5=5 |
1000 |
6 |
1001 |
7 |
1010 |
F6=8 |
10000 |
где k1 >= k2+2, k2 >= k3+2, ... , kr >= 2
Отсюда следует, что любое число можно однозначно записать в фибоначчиевой системе счисления, например:
Перевод числа в фибоначчиеву систему счисления осуществляется простым "жадным" алгоритмом: просто перебираем числа Фибоначчи от больших к меньшим и, если некоторое , то входит в запись числа , и мы отнимаем от и продолжаем поиск.
Надо написать программу для перевода натурального числа N в фибоначчиеву систему счисления.
Формат входных данных
Первая строка входного файла содержит натуральное число N (1≤N≤231-1).
Формат выходных данных
Выходной файл должен содержать строку, содержащую код Фибоначчи числа N.
Пример входного и выходного файлов
Пример входных данных |
Пример выходных данных |
12 5 |
10101 1000 |
Критерии оценивания задачи: каждому участнику олимпиады выдается два теста с одним небольшим (не больше ста) и одним большим числом. Тест с небольшим числом оценивается в 40 баллов, с большим числом оценивается в 60 баллов. Максимальное количество баллов 100.