Python-сообщество

“Чтобы мозг не заржавел, его надо упражнять” (С) мой бывший препод по вышке.

Предлагаю порешать простенькие програмистские задачки, типа “олимпиадных”. Естессно на пайтоне.
Опытным программистам - потренироваться, молодым посмотреть как будет “pythonic-way”

Задачки для затравки, весьма простые и стандартные:

1. “Банкомат”
В банкомат заряжаются купюры различных номиналов в неограниченном количестве.
Клиент хочет снять сумму в М грн.
Задача: выдать сумму (если можно) минимальным числом банкнот. или выдать сообщение о невозможности. (номиналы купюр задаются списком, на выходе - число купюр каждого номинала или сообщение об отсутствии решения)
Задача 1.а: решить задачу 1, с учетом ограниченности числа купюр (список купюр в банкомате задачется кортежами достоинство:количество купюр, на выходе - число купюр каждого номинала или сообщение об отсутствии решения)

2. “Тройский язык”
В тройском языке существует всего 3 баквы: a, b и с. Из них составляются слова длинной в 20 букв. “Божественными” называются слова в которых отсутсвуют подряд идущие повторяющиеся подпоследовательности (напр. abcaba…. - “божественное”, abcbc… - нет, повторяется “bc”).
Найти общее число “божественных” слов.

3. “Манускрипт”
Известный автор написал новую книгу “Дзен-буддизм Пайтон”, которая состоит из N глав. Количество страниц в каждой главе различно (задается списком). Издательство решило издать эпохальный труд в M томах. Цель: скомпоновать главы по томам так, чтобы объем томов как можно меньше отличался.
Вывести номера глав, входящих в каждый том.

ЗЫ Если тема тупая - снесите нафик :-)
ЗЗЫ если не тупая, решаем, предлагаем свои решения.

последняя задача меня давно мучает
первая вроде совсем легкая

Вторая задача

# -*- coding: cp1251 -*-
def Bojestvennost(slovo):
N=len(slovo)
for i in range(2,N+1):
#print ‘i=’,i
for j in range(1,(i)/2+1):
#print ‘j=’,j
#print ‘"’+slovo+'“ ”'+slovo+'"'
if slovo==slovo:
return False
return True

def Objed(slova1, slova2):
slova=
for slovo1 in slova1:
slova+=
return slova

po1=
po2=Objed(po1,po1)
print ‘Двоек:’, len(po2)
po4=Objed(po2,po2)
print ‘Четвёрок:’, len(po4)
po8=Objed(po4,po4)
print ‘Восьмёрок:’, len(po8)
po16=Objed(po8,po8)
print ‘Шестнадцаток:’, len(po16) # Интересно, есть такое слово?
po20=Objed(po16,po4)
print ‘Двадцаток:’, len(po20)

Выводит:

Двоек: 6
Четвёрок: 18
Восьмёрок: 78
Шестнадцаток: 798
Двадцаток: 2388

Первая задача:

# -*- coding: cp1251 -*-

def Razmen(M,D):
if M<=0:
print “Сумма должна быть положительной!”
return
tablica=*(M+1)
for i in range(1,M+1):
rzm=None
for j in D:
rzmj=None
if i>j and tablica:
lenj,rzmj=tablica
lenj+=1
rzmj=rzmj+
elif i==j:
rzm=(1,)
break
if rzm and rzmj:
rzm=min(rzm, (lenj,rzmj))
elif rzmj:
rzm=(lenj,rzmj)
tablica=rzm
if tablica:
razmen={}
for i in tablica:
if razmen.has_key(i):
razmen+=1
else:
razmen=1
return razmen
else:
print “Нет решения”


Выдаёт:

>>> Razmen(867,[2,5,10])
{2: 1, 10: 86, 5: 1}
>>> Razmen(11,[3,10])
Нет решения
>>> Razmen(23,[3,10])
{10: 2, 3: 1}

Striver
вторая красиво, но не совсем оптимально будет :-) лучше сразу 20-ки генерировать
а первая - близко к идеалу :-) особенно спасибо за чистый python-way
и рекурсии тут накакой не надо :-) рекурсия нужна если стоит задача (как в SICP) посчитать общее число вариантов размена. а тут - просто найти оптимальный. решается без рекурсии.
кстати такой алгоритм зовется “жадным”.

cleg
Если сразу двадцатки генерировать, то их 3**20=3486784401L слишком много, я пробовал пустой цикл столько раз крутить, достало ждать, тормознул раньше, а тут ведь ещё проверять надо…

3 задача определена неточно. “чтобы объем томов как можно меньше отличался” может означать:
1) минимальное среднее отклонение
2) минимальную дисперсию
3) минимальную разницу кол-ва страниц самого толстого тома и самого тонкого (остальные побоку)
4) а может ещё что-то означать…

Моё решение первой задачи

def GetMoney(m, nom_list):
m = int(m)
if m < 0:
print “m - Incorrect value”
return
nom_list =
nom_list.sort(reverse=True)
res = {}
for nom in nom_list:
num = m / nom
res = num
m = m - nom * num
if m:
print “Can not find solution”
return
return res

Результат

>>> GetMoney(347, (2,5,10))
{10: 34, 2: 1, 5: 1}
>>> GetMoney(9, (2,5,10))
{10: 0, 2: 2, 5: 1}
>>> GetMoney(9, (5,10))
Can not find solution

Viper: Моё решение первой задачи
def GetMoney(m, nom_list):

Вот именно это называется “жадным алгоритмом” (мы все обычно так деньги отсчитываем, сначала крупные) . Он самый быстрый, но к сожалению не обрабатывает некоторые ситуации:

GetMoney(12,)
Can not find solution

А в идеале должно быть {3:4}

Striver
3 задача определена неточно. “чтобы объем томов как можно меньше отличался” может означать:

Striver
Он самый быстрый, но к сожалению не обрабатывает некоторые ситуации: