Задачи за тренинг

Задача 2а. K-та редица на Фибоначи Gk дефинираме по следния начин (k > 0):
                      Gk(n) = Gk(n-1) + Gk(n-2) + ... + Gk(n-k)
за n > = k при зададени 
(1)                  Gk(0), Gk(1), ... , Gk(k-1). 
Да се напише програма за проверка дали дадено число е елемент от такава редица и ако е елемент, да се намери индексът му в редицата. Оригиналната редица на Фибоначи се получава при k=2 и G2(0) = G2(1) = 1.

Вход:
На първия ред се задава редица от k числа, които са първите членове на редицата.
На следващия ред са дадените числа за проверка. По същия начин се задават няколко примера. Всички числа са цели в интервала [0, 1000].

Изход:

За всяко число за проверка (от входа) се извежда индексът на числото (неотрицателно цяло число), ако е член на редицата, и -1, ако не е член на редицата. Ако числото се среща 2 или повече пъти в редицата, извежда се най-малкия индекс. Числата за всеки пример от входа са на един ред с разделител интервал, а за различни примери - на различни редове.

Пример:
1 1
2 10 55 4 1
1 2 1
1 12 23 5

Решение на примера:
2 -1 9 -1 0
0 5 6 -1


Задача 2b. Дадена е проста дроб. Напишете програма, която съкращава дробта до несъкратим вид,  т.е. намира несъкратима дроб, равна на дадената.

Стандартен вход:
Всеки пример се задава с израза m/n, където m  и n са две естествени числа, по-малки от 105 - съответно числител и знаменател  на проста дроб. Входът съдържа няколко примера.

Стандартен изход:
За всеки пример на изхода се записва несъкратимата дроб по същия начин, както е зададена на входа. Когато решението е цяло число, то се записва по нормалния начин.

Пример:

12/8 10/20 21/7 1/7 8/8

Решение на примера:
3/2 1/2 3 1/7 1