Для членов жюри Решение и тесты к заданиям II (муниципального) этапа Конкурса по программированию и информационным технологиям

27 февраля 2013 г.

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

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

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

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

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

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

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

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

Пример входных данных	Пример выходных данных
12 5	10101 1000

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