» »

[python] project euler problem

[python] project euler problem

A110 ::

Začel sem z project euler ampak pri 4 problemu ne vem zakaj mi vrne preveliko stevilo. mnozim 2 3 mestni številki torej bi moral dobiti kvečjemu 6 mestno številko vrne pa veliko večjo. bi mi lahko kdo prosim našel napako v kodi? Naloga pa je Find the largest palindrome made from the product of two 3-digit numbers.
def prezrcali(s):
    niz = ""
    dolzina = len(s)
    for i in range (0, dolzina):
        niz = niz + s[dolzina -1-i]
    return niz


a = 100
b = 100
niz = []
for i in range (0,899):
    a = a + i
    for k in range (0,899):
        b = b + k
        c = a * b

        if str(c) == prezrcali(str(c)):
            niz = niz +[c]
print(niz)
print (max(niz))
input()

Dpool ::

Ja saj pa prvem loopu dodajaš zraven a-ju vedno novo vrednost (k stari vrednosti).

Recimo:

a = 100;

i = 800;

a = 100 + 800 = 900;

naslednji krog for-a:

a = 900;

i = 801;

a = 900 + 801 = 1701;

itd.

Zgodovina sprememb…

  • spremenil: Dpool ()

Dpool ::

for (i = 0; i< 899; i++)
a++;
for (k = 0; k < 899; k ++)
b++;
c = a * b;


Uporabil sem "Javo" za primer. Mislim da bi tako moralo delovati. Če nočeš da začne a z 101, ampak s 100 in enako za b..potem nastavi a in b pred loopom na 99. Ali pa čekiraj znotraj for-a, če je i=0, če je, potem ne incrementaj vrednosti.

Zgodovina sprememb…

  • spremenil: Dpool ()

A110 ::

sem spremenil iz a = a + i v a = a+1 da gre vedno za eno gor in enako pri bju ampak se vedno vrne veliko preveliko stevilko. pac ni mi jasno zakaj. kolikor razumem kar sem napisal začne pri a = 100 in potem preveri produkte med 100 in bjem ki zavzame vse vrednost med 100 in 999. potem spremeni a v 101 in ponovno preveri vse moznosti b-ja in tako dalje dokler ne preveri vseh moznih produktov dveh tromestnih stevil. pa tudi ce rocno iz seznama vseh poiscem najvecjo 6 mestno stevilo resitev ni pravilna tako da ocitno nekaj ne dela prav. bolj kot sama resitev me zanima zakaj ne dela oz. kje je napaka in ali morda narobe razmisljam

HotBurek ::

Napako imaš v vrstici 13 in 15.

import time;

def prezrcali(s):
    niz = ""
    dolzina = len(s);
    for i in range(0, dolzina):
        niz = niz + s[dolzina - 1 - i];
    return niz;

a = 100;
b = 100;
niz = [];
for i in range(0, 899):
    _a = a + i;
    for k in range(0, 899):
        _b = b + k;
        c = _a * _b;
        if str(c) == prezrcali(str(c)):
            niz.extend([c]);
        print ("a=" + str(_a) + " | b=" + str(_b) + " | c=" + str(c) + " | nc=" + str(len(niz)));

print("Sleeping 5 seconds...");
time.sleep(5);

niz.sort();

count = 1;

for n in niz:
    print(str(count) + "/" + str(len(niz)) + " | " + str(n));
    count = int(count) + 1;
    time.sleep(0.1);



Še rezultat na koncu (998*998):

2466/2470 | 886688
2467/2470 | 888888
2468/2470 | 888888
2469/2470 | 906609
2470/2470 | 906609
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window

Zgodovina sprememb…

  • spremenilo: HotBurek ()

FriK25 ::

Kot je že napisal HotBurek imaš napako v teh dveh vrsticah ker povečuješ sami števili in ti zrastejo do (899+899=1798) na števec. Spodaj bom prilepil še svojo verzijo če ti pomaga.


def palindromic_number(min=100,max=999):
    max_palindrome = 0
    for a in range(min,max + 1):
        for b in range(a + 1, max + 1): # izogibamo se duplikatom
            prod = a*b
            if prod > max_palindrome and str(prod)==(str(prod)[::-1]):
                max_palindrome = prod
    return max_palindrome
 
L = palindromic_number()
 
print (L)

A110 ::

to da preveč povečujem sem će popravil da povečujem samo za 1 zdaj imam:
def prezrcali(s):
    niz = ""
    dolzina = len(s)
    for i in range (0, dolzina):
        niz = niz + s[dolzina -1-i]
    return niz


a = 100
b = 100
niz = []
for i in range (0,900):
    a = a + 1
    for k in range (0,900):
        b = b + 1
        c = a * b

        if str(c) == prezrcali(str(c)):
            niz = niz +[c]
print(niz)
print (max(niz))
input()
ampak se vedno vrača veliko prevelika stevila. glede duplikatov pa vem da so, ampak mislim da vseeno nebi smelo vplivati na resitev pritem primeru

Zgodovina sprememb…

  • spremenilo: A110 ()

HotBurek ::

a = 100;
a = a + 1;

Tu je problem.

1. rešitev
Rezultat a+1 shraniš v drugo spremenjlivko. Moj primer ima _a, tako da ne povoziš a, ki mora ostati 100. V tvojem primeru se a povečuje (101, 103, 105, "110", "120", "140" itn...).
2. rešitev
niz = []
for i in range (0,900):
    a = 100
    a = a + 1
    for k in range (0,900):
        b = 100
        b = b + 1
        c = a * b
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window

FriK25 ::

Tukaj ne uporabljaš prav števcev printaj si ven B dobiš dosti več kot 1000 :) pomisli zakaj je tako


EDIT: HotBurek ti je prigranil mindstormanje

Zgodovina sprememb…

  • spremenil: FriK25 ()

A110 ::

sem poenostavil zadevo in deluje :)
def prezrcali(s):
    niz = ""
    dolzina = len(s)
    for i in range (0, dolzina):
        niz = niz + s[dolzina -1-i]
    return niz



niz = []
for i in range (100,1000):
    for k in range (100,1000):
       c = i * k
       if str(c) == prezrcali(str(c)):
            niz = niz +[c]
print(niz)
print (max(niz))
input()

HotBurek ::

Še ena varianta, z izpisom in barvami. :)

import time;

def prezrcali(s):
    niz = ""
    dolzina = len(s)
    for i in range(0, dolzina):
        niz = niz + s[dolzina - 1 - i]
    return niz


niz = [];
max = 0;
count = 0;
countmax = 900*900;
for i in range(100, 1000):
    for k in range(100, 1000):
        c = i * k;
        count = int(count) + 1;
        percent = str(int((count/countmax)*100));
        if str(c) == prezrcali(str(c)):
            niz = niz + [c]
            if c > int(max):
                max = c;
                print(str(i) + "*" + str(i) + "= " + "\033[92m" + str(c) + " | " + str(prezrcali(str(c))) + "\033[0m" + "\033[95m" + " | " + str(max) + "\033[0m" + " | " + "\033[94m" + str(count) + "/" + str(countmax) + " " + percent + "%" + "\033[0m");
                time.sleep(0.4);
            else:
                print(str(i) + "*" + str(i) + "= " + "\033[92m" + str(c) + " | " + str(prezrcali(str(c))) + " | " + "\033[0m" + " | " + str(max) + " | " + "\033[94m" + str(count) + "/" + str(countmax) + " " + percent + "%" + "\033[0m");
        else:
            print(str(i) + "*" + str(k) + "= " + "\033[91m" + str(c) + " | " + str(prezrcali(str(c))) + "\033[0m" + " | " + str(max) + " | " + "\033[94m" + str(count) + "/" + str(countmax) + " " + percent + "%" + "\033[0m");
time.sleep(1);
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window

Zgodovina sprememb…

  • spremenilo: HotBurek ()

HotBurek ::

FriK25, hvala za ta del kode:

if prod > max_palindrome and str(prod)==(str(prod)[::-1]):


Nisem poznal funkcije text[::]. Mogoče pride kdaj prav. :)

Da dodam en testič:
text = "A)B:CxDuEsF-GnHoIhJtKyLP";
print();
print(text);
print("---");
print(str(text)[0::1]);
print(str(text)[len(text)::-1]);
print(str(text)[0::2]);
print(str(text)[1::2]);
print(str(text)[len(text)::-2]);


Printout:
A)B:CxDuEsF-GnHoIhJtKyLP
---
A)B:CxDuEsF-GnHoIhJtKyLP
PLyKtJhIoHnG-FsEuDxC:B)A
ABCDEFGHIJKL
):xus-nohtyP
Python-sux:)


Sem se pa lotil naloge 5. Za pogoj 1-10 je rezultat 2520. Spodnja ("trotl ziher, 1 po 1" varianta) varianta program pride do 1-19 v približno 9 minutah. Do 20 pa še nisem čakal dovolj časa. :)

Evo, še koda, če komu pride prav:
import time;
import datetime;

a = 9.9;
print();
print("a = 9.9;");
print("str(a) = " + str(a));
print("str(int(a)) = " + str(int(a)));
print();

upto = 20;
for i in range(1,upto + 1):
    dlist = [];
    for j in range(1,i + 1):
        dlist.extend([j]);

    start = time.strftime("%H:%M:%S");

    num = 1;
    while True:
        ok = True;
        for i in dlist:
            _div = num/i;
            if _div != int(_div):
                ok = False;
                break;
        if ok:
            end = time.strftime("%H:%M:%S");
            diff = datetime.datetime.strptime(end, "%H:%M:%S") - datetime.datetime.strptime(start, "%H:%M:%S");
            print(str(num) + " | 1-" + str(i) + " | time taken= " + str(diff));
            break;
        num = int(num) + 1;
time.sleep(1);
print();
print("Done");


Print out:
1 | 1-1 | time taken= 0:00:00
2 | 1-2 | time taken= 0:00:00
6 | 1-3 | time taken= 0:00:00
12 | 1-4 | time taken= 0:00:00
60 | 1-5 | time taken= 0:00:00
60 | 1-6 | time taken= 0:00:00
420 | 1-7 | time taken= 0:00:00
840 | 1-8 | time taken= 0:00:00
2520 | 1-9 | time taken= 0:00:00
2520 | 1-10 | time taken= 0:00:00
27720 | 1-11 | time taken= 0:00:00
27720 | 1-12 | time taken= 0:00:00
360360 | 1-13 | time taken= 0:00:01
360360 | 1-14 | time taken= 0:00:01
360360 | 1-15 | time taken= 0:00:01
720720 | 1-16 | time taken= 0:00:01
12252240 | 1-17 | time taken= 0:00:30
12252240 | 1-18 | time taken= 0:00:28
232792560 | 1-19 | time taken= 0:09:06
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window

Zgodovina sprememb…

  • spremenilo: HotBurek ()

HotBurek ::

Zdaj so tudi rezultati do 20:
12252240 | 1-17 | time taken= 0:00:27
12252240 | 1-18 | time taken= 0:00:28
232792560 | 1-19 | time taken= 0:08:43
232792560 | 1-20 | time taken= 0:08:43

Možno, da so pravi :) Rabi pa 8-9 minut.


htop pokaže, da vse skupaj teče samo na enem jedru:

 htop

htop



Za pohitritev mogoče 8 skript (oz. kolikor je jeder) vzporedno, vsaka pa preveri 1/8 od vseh števil.
skripta1=[1,9,17,25,...]
skripta2=[2,10,18,26,...]
skripta3=[3,11,19,27,...]
skripta4=[4,12,20,28,...]
skripta5=[5,13,21,29,...]
skripta6=[6,14,22,30,...]
skripta7=[7,15,23,31,...]
skripta8=[8,16,24,32,...]
root@debian:/# iptraf-ng
fatal: This program requires a screen size of at least 80 columns by 24 lines
Please resize your window

Randomness ::

@HotBurek: Srednja šola?

Rabi pa 8-9 minut.
Implementacija je obupno počasna.
Za pohitritev mogoče 8 skript (oz. kolikor je jeder) vzporedno, vsaka pa preveri 1/8 od vseh števil.
Razmišljaj raje v smeri, kako bi izboljšal algoritem.

Dpool ::

Zrcaljenje vzame največ časa, ker za vsako novo števko se sproži postopek iteracije posameznih števk, da se obrne vrstni red.

Možne optimizacije:
- Preden začneš algoritem zrcaljenja lahko narediš check če se prva števka ujema z zadnjo (če se ne, sploh ne rabiš nič zrcalit, samo skipp
- Algoritem zrcaljenja: Palindrom pomeni, da če obrneš vrstni red števk, je številka še vedno ista (1221).
--> 3 števke v številu: preveri samo ali je prva števka enaka zadnji števki, le takrat je palindrom (222, 121, 909 .. in NE 122, 331,..)
--> 4 števke v številu: razdeliš celotno 4-mestno števko na polovico in sešteješ dve števki (tj prvi dve števki in zadnji dve števki). Če je vsota teh dveh seštevanj enaka, je palindrom.
--> 5 števk v številu: isto kot za 4 števke v številu..saj sredinsko število ni važno da palindrom velja (12321)

Upam, da nisem preveč zasral, ker iz glave pišem in se nisem poglabljal kaj dlje v palindrome (možno da obstajajo že kakšni optimizacijski algoritmi). Zgoraj izhajam iz predpostavke, da je časovno manj zapravno, če ne preverjaš celotnega niza zmeraj, ampak to poskusiš razčlenit na čim manj operacij (pri tvoji funkciji za zrcaljenje pa npr greš skozi vsak člen array-a in ga celo vpisuješ v nov array, zelo časovno potratno).

Se opravičujem za morebitne napake oz. če sem kje kaj spregledal kakšno pravilo palindroma ali pa spregledal kak primer, ki izključuje moje zgornje predpostavke.

Spura ::

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

1, 2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5. Torej je potrebni prafaktorji za to, da je deljivo z vsemi 1-10 je 2*2*2*3*3*5*7 = 2520.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Zanka z zajemanjem števk

Oddelek: Programiranje
6638 (323) misticnimrk
»

pomoč pri nalogi

Oddelek: Programiranje
13740 (299) SloKin
»

Python - težava s slovarji - vnos

Oddelek: Programiranje
5813 (635) RatedR
»

Python

Oddelek: Programiranje
202142 (828) d_DJ
»

Iskanje podvojenih zaporedij

Oddelek: Programiranje
91313 (1093) Gundolf

Več podobnih tem