Griffon
Сен. 28, 2009 22:58:12
Питон тройка
def is_polinom(ivalue):
value = list(str(ivalue))
reverse = value[:]
reverse.reverse()
return value == reverse
def get_max_polinom(length=3):
i1 = int("9" * length)
count = 0
for i in filter(lambda x: x % 5, range(i1, 0, -2)):
last = i % 10
corrector = 0
if last == 1: corrector = 8
if last == 9: corrector = 2
for j in range(i+corrector, i1+1, 10):
count += 1
test_val = i * j
if is_polinom(test_val):
return test_val, "=", i, "*", j, ", count =", count
print(*get_max_polinom(3))
ред… кстати скорость выполнения, для длины в три символа, такая же как и при старом алгоритме с шестью тысячами итераций. Но для чисел большей длины конечно же скорость намного выше.
FILLIPO
Сен. 29, 2009 17:31:25
Ухты.
(простите за бессмысленность)
pasaranax
Сен. 29, 2009 19:58:46
print max([(p*q, p, q) for p in xrange(999, 100, -1) for q in xrange(p, 100, -1) if str(p*q) == str(p*q)[::-1]])
возник вопрос: можно ли как-то изнутри этого генерирующегося списка обратиться к его уже готовым элементам и/или остановить его генерацию на каком-то шаге?
п.с. Предлагаю еще какую-нибудь задачу разыграть
DeFoR
Сен. 30, 2009 12:40:44
Еще из этой задачи не все выжато
906609= 913* 993 за 109
999900665566009999 =999920317 *999980347 за 98 701 221
def gen1(num):
while num>0:
x= 2 if num%10 in (0,7,5,2) else 1
num-=x
yield num
def gen2(num1,num2):
tmp1=num2%10
tmp2=num2*2
d1={2:8,7:8,3:4,8:4}
d={9:8,1:2,7:10,3:10}
if tmp1 in (0,5):
yield num1, tmp2-num1
else:
num1+=d1
while num1>num2:
num1-=d
yield num1 , tmp2-num1
num=0
N=999999
for i in gen1(N):
for y,x in gen2(N,i):
tmp1=str(y*x)
num+=1
if tmp1==tmp1:
print tmp1, y, x, num
raise
Решил проверить на больших числах и вот что получилось:
3 906609 993 913 109
4 99000099 9999 9901 120
5 9966006699 99979 99681 1 228
6 999000000999 999999 999001 10 200
7 99956644665999 9998017 9997647 189 204
8 9999000000009999 99999999 99990001 1 002 000
9 999900665566009999 999980347 999920317 98 701 221
10 99999834000043899999 9999996699 9999986701 2 759 580
11 9999994020000204999999 99999996349 99999943851 35 773 090
до 9 разрядных все стройно но с 10 разрядных не то
FILLIPO
Сен. 30, 2009 18:18:22
Расскажите, пожалуйста, как сделать вот такую вещь:
есть список из цифр, например:
нужно составить все возможные произведения этих цифр, т.е. например 1 * 3 == 3; 1 * 78 * 97 == 7566 и так далее.
как это сделать, не знаю. Расскажите?
DeFoR
Сен. 30, 2009 20:23:30
Можно попробовать так
функция возвращает все сочетания, ну а там уже дело техники можно перемножить через reduce
def gen(tp):
raz=len(tp)
d=
q=
for i in filter(lambda x: x not in d, range(2**raz)):
if i:
tmp1=i
n=0
c=
while tmp1>0:
tmp1,tmp2=tmp1/2,tmp1%2
if tmp2: c+=[tp,]
n+=1
q+=
print q
zx=
gen(zx)
Griffon
Сен. 30, 2009 22:46:20
Cделал перебором.
def do(l):
l1 = [(x,) for x in l]
result = []
while True:
x = l1.pop(0)
if len(x) == len(l):
return set(result)
pre_res = []
for i in l:
buf = list(x)
buf.append(i)
buf.sort()
pre_res.append(tuple(buf))
l1.extend(pre_res)
result.extend(pre_res)
DeFoR, интересный метод. Ещё можно сократить на 17 итераций при длине в три символа. Или даже на 18 :)
Там при старте внутреннего цикла два раза подряд идёт одна и та же пара. И самое первое значение (одно из) больше чем 999.
DeFoR
Окт. 1, 2009 08:53:02
Помоему в алгоритме перебором есть ошибка
общее количество разнообразных сочетаний из 5 елементов находится как сумма сочетаний по 2 из 5 , 3 из 5, 4 из 5 и 5из 5
C_n^m` = `{n!}/{m! (n-m)!}
тобишь 10+10+5+1=26
я попробовал запустить вашу функцию
print len(do())
получил 246 наборов
с 999 да согласен можно и еще уменьшить, при первом запуске я получил 100 итераций, но остальные разрядности непошли, пришлось подкоректировать, возможно несовсем оптимально получилось корректировка.
Griffon
Окт. 1, 2009 17:44:44
Да. Я почему то считал что можно умножать число само на себя.
Вот так правильно:
def do(l):
start = set([(x,) for x in l])
l1 = set(start)
full = set(l)
result = set()
while l1:
x = l1.pop()
result.add(x)
new_l = full.difference(x)
for i in new_l:
buf = set(x)
buf.add(i)
l1.add(tuple(buf))
return list(result.difference(start))
ZZZ
Окт. 1, 2009 18:01:42
Griffon, код неправилен. Да, он работает, но переводить int в str… Давай математически.
def is_palindrome(n):
digits = []
while n > 0:
n, o = divmod(n, 10)
digits.insert(0, o)
if len(digits) % 2 == 0:
l = digits[len(digits)/2:]
else:
l = digits[len(digits)/2 + 1:]
l.reverse()
return digits[:len(digits)/2] == l
Это моё и не очень красивое решение.
Дальше. Откуда у тебя столько интересный допущений? Где доказательства?
Объясни алгоритм словами…
Вот мой вариант:
if __name__ == "__main__":
m = 1
for i in xrange(1000, 100, -1):
for ii in xrange(i+1, 100, -1):
if i * ii < m:
break
if is_palindrome(i * ii):
if i * ii > m:
m = i * ii
break
print m
Это почти элементарный перебор.