DjangoBB LoFi version

Viper

Апрель 6, 2007 01:40:47

Striver
но к сожалению не обрабатывает некоторые ситуаци

мда…это я провтыкал :(.
Но вроде поправил :)

def GetMoney(m, nom_list):
def get(m, nom_list):
res = {}
for nom in nom_list:
num = m / nom
res = num
m = m - nom * num
return res, m
m = int(m)
if m < 0:
print “m - Incorrect value”
return
nom_list =
nom_list.sort(reverse=True)
res, m = get(m, nom_list)
while m:
n = -2
while 1:
try:
if res[nom_list]:
break
n -= 1
except IndexError:
print “Can not find solution”
return
res[nom_list] -= 1
m += sum([i*res for i in nom_list], nom_list)
tmp, m = get(m, nom_list)
res.update(tmp)
return res

for i in xrange(1, 25):
res = GetMoney(i, (3, 5, 10))
if res:
print i, ‘-’, res

Результат

Can not find solution
Can not find solution
3 - {10: 0, 3: 1, 5: 0}
Can not find solution
5 - {10: 0, 3: 0, 5: 1}
6 - {10: 0, 3: 2, 5: 0}
Can not find solution
8 - {10: 0, 3: 1, 5: 1}
9 - {10: 0, 3: 3, 5: 0}
10 - {10: 1, 3: 0, 5: 0}
11 - {10: 0, 3: 2, 5: 1}
12 - {10: 0, 3: 4, 5: 0}
13 - {10: 1, 3: 1, 5: 0}
14 - {10: 0, 3: 3, 5: 1}
15 - {10: 1, 3: 0, 5: 1}
16 - {10: 1, 3: 2, 5: 0}
17 - {10: 0, 3: 4, 5: 1}
18 - {10: 1, 3: 1, 5: 1}
19 - {10: 1, 3: 3, 5: 0}
20 - {10: 2, 3: 0, 5: 0}
21 - {10: 1, 3: 2, 5: 1}
22 - {10: 1, 3: 4, 5: 0}
23 - {10: 2, 3: 1, 5: 0}
24 - {10: 1, 3: 3, 5: 1}

Striver

Апрель 6, 2007 08:19:59

Ну раз за 3 задачу никто не берётся, придётся мне. Рекурсивным алгоритмом создаётся весь список вариантов, потом они сравниваются.

# -*- coding: cp1251 -*-

def Raspred1(N, M):
“Строим списки разрывов между главами”
if M==1:
return []
if N<M:
return
if N==M:
return
ret=
for i in range(M-1,N):
rsp=Raspred1(i,M-1)
ret+=[x+ for x in rsp]
return ret

def Perevod(N, ls):
“Переводим списки к виду, данному в задании”
newlist=
for i in ls:
i1=+i
i2=i+
newlist.append(map(range,i1,i2))
return newlist

def Kriteriy1(strTom):
“Разница самых толстого и тонкого томов”
return max(strTom)-min(strTom)

def Kriteriy2(strTom):
“Среднеквадратичное отклонение (точнее его квадрат)”
srednee=float(sum(strTom))/len(strTom)
return sum()

Kriteriy=Kriteriy2

def Raspred(strs,M):
N=len(strs)
raspredelenia = Raspred1(N, M)
print u“Размер списка:”, len(raspredelenia)
raspredelenia = Perevod(N, raspredelenia)
straniz_v_tomah = [[sum([strs for x in y]) for y in z] for z in raspredelenia]
otlichaemoct = map(Kriteriy, straniz_v_tomah)
minindex = otlichaemoct.index(min(otlichaemoct))
return raspredelenia

результат:

>>> from random import randint
>>> strs=map(randint, [1]*30, [1000]*30)
>>> strs
[581, 48, 902, 463, 763, 250, 795, 132, 962, 189, 717, 721, 717, 379, 235, 489, 53, 390, 911, 201, 434, 248, 430, 677, 568, 712, 426, 526, 35, 957]
>>> Raspred(strs, 3)
Размер списка: 406
[[0, 1, 2, 3, 4, 5, 6, 7, 8], [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], [20,21, 22, 23, 24, 25, 26, 27, 28, 29]]
>>> Raspred(strs, 5)
Размер списка: 23751
[[0, 1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15, 16, 17], [18, 19, 20, 21, 22, 23], [24, 25, 26, 27, 28, 29]]
>>> Raspred(strs, 6)
Размер списка: 118755
[[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13], [14, 15, 16, 17, 18, 19], [20, 21, 22, 23, 24], [25, 26, 27, 28, 29]]

Raspred(strs, 7) я так и не дождался, размер списка растёт экспоненциально. По идее нужен какой-то итеративный алгоритм, чтобы при создании очередного варианта, сравнивать его сразу и выкидывать худший, а не хранить весь огромный список, тогда хоть память лошадиными дозами бы не тратилась, но вот как это сделать???

Viper

Апрель 6, 2007 09:15:46

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

def GetMoney1a(m, *args):
def get(m, nom_list, nom_dict):
res = {}
for nom in nom_list:
num = m / nom
num = min((num, nom_dict))
tmp = m - nom * num
if num and (tmp and tmp < nom_list):
num -= 1
tmp = m - nom * num
res = num
m = tmp
return res, m
m = int(m)
if m < 0:
print “m - Incorrect value”
return
nom_dict = dict(((int(k), int(v)) for k, v in args))
nom_list = nom_dict.keys()
nom_list.sort(reverse=True)
res, m = get(m, nom_list, nom_dict)
while m:
n = -2
try:
while not res[nom_list]:
n -= 1
except IndexError:
print “Can not find solution”
return
res[nom_list] -= 1
m += sum((i*res for i in nom_list), nom_list)
tmp, m = get(m, nom_list, nom_dict)
res.update(tmp)
return res

for i in xrange(35, 47):
print i, ‘-’,
res = GetMoney(i, (3, 5, 10))
if res:
print res,
res1a = GetMoney1a(i, (3,10), (5,1), (10,1))
if res1a:
print res1a

Результат

35 - {10: 3, 3: 0, 5: 1} {10: 0, 3: 10, 5: 1}
36 - {10: 3, 3: 2, 5: 0} {10: 1, 3: 7, 5: 1}
37 - {10: 2, 3: 4, 5: 1} {10: 1, 3: 9, 5: 0}
38 - {10: 3, 3: 1, 5: 1} Can not find solution
39 - {10: 3, 3: 3, 5: 0} {10: 1, 3: 8, 5: 1}
40 - {10: 4, 3: 0, 5: 0} {10: 1, 3: 10, 5: 0}
41 - {10: 3, 3: 2, 5: 1} Can not find solution
42 - {10: 3, 3: 4, 5: 0} {10: 1, 3: 9, 5: 1}
43 - {10: 4, 3: 1, 5: 0} Can not find solution
44 - {10: 3, 3: 3, 5: 1} Can not find solution
45 - {10: 4, 3: 0, 5: 1} {10: 1, 3: 10, 5: 1}
46 - {10: 4, 3: 2, 5: 0} Can not find solution

cleg

Апрель 6, 2007 09:31:26

Продолжать будем? :-)

Striver

Апрель 6, 2007 09:39:54

Вот повеселее задачка.
Дано игровое поле 4x4:

К М Р Д , где С - стена, П - Пещера, они не двигаются.
Г Р М С К - копейщик, Р - рыцарь
С Р К Г М - маг, Г - гном
П М С К Д - дракон

Правила: Можно менять местами: Д с М, М с Г, Г с К, К с Р.
Цель - завести дракона в пещеру, т.е. поставить его рядом с ней.
Программа должна вывести поледовательность обмена фишек.

Этот прикол взят из одной игрушки-квеста, по идее они там предполагали, что весь путь нужно в уме найти, но на это, по-моему, только сверхчеловек способен… Когда я её проходил, моих мозгов на это не хватило, поэтому я программу писал.

cleg

Апрель 6, 2007 11:18:16

и от меня задачка попроще :-)
недавно знакомый подкинул

кенгуренок может шагнуть на 1 м и прыгнуть на 3 м. двигаться он может только вперед.
сколькими принципиально различными способами он можей пройти расстояние в М метров?

ЗЫ задачу надо решить без рекурсии. поиска в ширину и т.п.

Striver

Апрель 6, 2007 11:44:00

А 1-3-1 и 1-1-3 принципиально различные способы?

cleg

Апрель 6, 2007 13:52:05

да.

Pelmen

Апрель 6, 2007 22:50:24

Striver тут нужны деревья, а не линейный алгоритм, вообще было много идей по поводу третьей задачи
ты самый неоптимальный выбрал, но с другой стороны самый точный

там например можно идти по отсортированному списку и подбирать то что не выходит за пределы, по идее самый быстрый и оптимальный, в зависимости от пары коэффициентов

Striver

Апрель 9, 2007 12:39:54

Итеративный перебор в третьей задаче:

# -*- coding: cp1251 -*-

def Sled(N, M, pred):
if N<=M:
return False
if pred=='1':
n1=0
while pred==1:
n1+=1
n0=n1-1
return pred+[pred+1]+[pred-1]+pred
else:
if pred>1:
return [pred+1]+[pred-1]+pred
n1=1
while n1<M and pred==1:
n1+=1
if n1==M:
return False
#print ‘n1=’,n1
return *(n1-1)+[pred+1]+[pred-1]+pred

def test(N, M):
ls=*(M-1)+
n=1
while ls and n<100:
print ls
ls=Sled(N, M, ls)
n+=1

def Kriteriy(strTom):
return max(strTom)-min(strTom)

def Perevod(ls):
n=0
ret=
for i in ls:
ret+=
n+=i
return ret

def Stranic(strs, ls):
return [sum([strs for x in y]) for y in ls]

def Raspred (strs, M):
N=len(strs)
if N<M:
return False
if M==1:
return
n=1
ls=*(M-1)+
lsp=Perevod(ls)
krit=Kriteriy(Stranic(strs, lsp))
while True:
if n%10000 == 0:
print ‘n=’,n
ls=Sled(N, M, ls)
if not ls:
break
lsp1=Perevod(ls)
krit1=Kriteriy(Stranic(strs, lsp1))
if krit1<krit:
lsp=lsp1
krit=krit1
n+=1
print ‘n=’,n, ‘kriteriy=’, krit
return lsp

Основная функция - Raspred. test(N,M) выводит все варианты для расстановок. Работает тоже не очень быстро (например при N=30, M=10 кол-во вариантов больше 10000000), но здесь память зазря не тратится. Пробовал некий вариант жадного алгоритма, но ерунда получается: то пустые тома в конце останутся, то, наоборот, на пару глав томов не хватает.