Seuraa 
Viestejä927
Liittynyt19.3.2005

Tämä on taas eräs Putkaposti: https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=lukut

Lyhyesti: On annettu joukko lukuja:

363 726 1089 1313 1452 1717 1798 1815 1919 2121 2156 2178 2189 2541 2626 2805
2904 2997 3131 3267 3297 3434 3630 3838 3993 4037 4092 4107 4191 4242 4257 4312
4334 4343 4356 4378 4407 4532 4646 4719 4747 4807 4949 5011 5055 5071 5082 5151
5214 5353 5423 5445 5454 5495 5610 5665 5731 5808 5819 5858 5951 5989 5994 6171
6248 6281 6429 6446 6468 6523 6534 6565 6567 6594 6721 6767 6868 6897 6919 7051
7077 7128 7139 7171 7227 7260 7381 7424 7474 7513 7623 7678 7831 7858 7878 7881
7909 7986 8041 8063 8074 8088 8107 8129 8162 8173 8184 8195 8214 8283 8316 8349
8382 8415 8453 8484 8514 8624 8649 8712 8756 8778 8814 8932 8987 8989 8990 8991
9053 9064 9075 9099 9101 9119 9141 9156 9191 9213 9251 9292 9309 9328 9361 9393
9438 9493 9515 9546 9595 9597 9603 9614 9667 9678 9757 9797 9801 9802 9834 9890
9898 9909.

Kullekin luvulle pitäisi löytää pienin positiivinen kokonaisluku siten, että annettu luku kerrottuna tällä luvulla aiheuttaa sen, että tulossa numerot ovat nousevassa tai laskevassa järjestyksessä. Kuulemma tämän voi tehdä sekunneissa. Mutta millainen on tehokas algoritmi?

Ratkaisin tämän hitaalla Python-koodilla, mutta nopeampi tapa on haussa. Toivottavasti saatte selvää kun palsta sotkee sisennykset:

def generate_all_numbers(length):
l = list()
for one in range(0,length):
for two in range(0,length-one):
for three in range(0,length-one-two):
for four in range(0,length-one-two-three):
for five in range(0,length-one-two-three-four):
for six in range(0,length-one-two-three-four-five):
for seven in range(0,length-one-two-three-four-five-six):
for eight in range(0,length-one-two-three-four-five-six-seven):
for nine in range(0,length-one-two-three-four-five-six-seven-eight):
for ten in range(0,length-one-two-three-four-five-six-seven-eight-nine):
if max(one,two,three,four,five,six,seven,eight,nine) > 0:
num1 = "1"*one+"2"*two+"3"*three+"4"*four+"5"*five+"6"*six+"7"*seven+"8"*eight+"9"*nine
num2 = "9"*one+"8"*two+"7"*three+"6"*four+"5"*five+"4"*six+"3"*seven+"2"*eight+"1"*nine+"0"*ten
l.append(int(num1))
l.append(int(num2))
return(list(set(l)))

def find_smallest_increasing(number, length):
ehd = -1
num = "0"
length += 1
for one in range(0,length):
for two in range(0,length-one):
for three in range(0,length-one-two):
for four in range(0,length-one-two-three):
for five in range(0,length-one-two-three-four):
for six in range(0,length-one-two-three-four-five):
for seven in range(0,length-one-two-three-four-five-six):
for eight in range(0,length-one-two-three-four-five-six-seven):
for nine in range(0,length-one-two-three-four-five-six-seven-eight):
if max(one,two,three,four,five,six,seven,eight,nine) > 0:
num = "1"*one+"2"*two+"3"*three+"4"*four+"5"*five+"6"*six+"7"*seven+"8"*eight+"9"*nine
if int(num) % number == 0:
if ehd == -1:
ehd = int(num)

Kommentit (9)

pöhl
Seuraa 
Viestejä927
Liittynyt19.3.2005

if int(num) < ehd:
ehd = int(num)
return(ehd)

def find_smallest_decreasing(number, length):
ehd = -1
num = "0"
length += 1
for one in range(0,length):
for two in range(0,length-one):
for three in range(0,length-one-two):
for four in range(0,length-one-two-three):
for five in range(0,length-one-two-three-four):
for six in range(0,length-one-two-three-four-five):
for seven in range(0,length-one-two-three-four-five-six):
for eight in range(0,length-one-two-three-four-five-six-seven):
for nine in range(0,length-one-two-three-four-five-six-seven-eight):
for zero in range(0,length-one-two-three-four-five-six-seven-eight-nine):
if max(one,two,three,four,five,six,seven,eight,nine) > 0:
num = "9"*one+"8"*two+"7"*three+"6"*four+"5"*five+"4"*six+"3"*seven+"2"*eight+"1"*nine+"0"*zero
if int(num) % number == 0:
if ehd == -1:
ehd = int(num)
if int(num) < ehd:
ehd = int(num)
return(ehd)

numbers = [363,726, 1313, 1452, 1717, 1798, 1815, 1919, 2121, 2156, 2189, 2541, 2626, 2805,
2904, 2997, 3131, 3297, 3434, 3630, 3838, 3993, 4037, 4092, 4107, 4191, 4242, 4257, 4312,
4334, 4343, 4378, 4407, 4532, 4646, 4719, 4747, 4807, 4949, 5011, 5055, 5071, 5082, 5151,
5214, 5353, 5423, 5454, 5495, 5610, 5665, 5731, 5808, 5819, 5858, 5951, 5989, 5994, 6171,
6248, 6281, 6429, 6446, 6468, 6523, 6565, 6567, 6594, 6721, 6767, 6868, 6897, 6919, 7051,
7077, 7128, 7139, 7171, 7227, 7260, 7381, 7424, 7474, 7513, 7678, 7831, 7858, 7878, 7881,
7909, 7986, 8041, 8063, 8074, 8088, 8107, 8129, 8162, 8173, 8184, 8195, 8214, 8283, 8316, 8349,
8382, 8415, 8453, 8484, 8514, 8624, 8649, 8756, 8778, 8814, 8932, 8987, 8989, 8990, 8991,
9053, 9064, 9075, 9099, 9101, 9119, 9141, 9156, 9191, 9213, 9251, 9292, 9309, 9328, 9361, 9393,
9438, 9493, 9515, 9546, 9595, 9597, 9603, 9614, 9667, 9678, 9757, 9797, 9802, 9834, 9890,
9898, 9909]

hardnumbers = [1089, 2178, 3267, 4356, 5445, 6534, 7623, 8712, 9801]

l = generate_all_numbers(20)
A = list()
for i in range(len(l)):
for j in range(len(numbers)):
if l[i] % numbers[j] == 0:
A.append(l[i])
B = list()
for j in range(len(numbers)):
best = int("9" * 2000)
for i in range(len(A)):
if A[i] % numbers[j] == 0:
if A[i] < best:
best = A[i]
print(str(numbers[j])+" "+str(best/numbers[j])+ " " + str(best))

for k in range(0,len(hardnumbers)):
number = hardnumbers[k]
a = -1
b = -1
i= 1
j= 1
while a == -1:
if a % 5 != 0:
a = find_smallest_increasing(number,i)
i = i + 1
b = -1
j = 1
while b == -1:
b = find_smallest_decreasing(number,max(i,j))
j = j + 1
print(str(number)+" "+str(min(a,b)/number)+" " + str(min(a,b)))

Merlin
Seuraa 
Viestejä4095
Liittynyt25.9.2017

Kuulostaa vähän unique sink problemilta johon törmäsin juuri. Se on ilmeisesti sellainen nothing is real tulos.

Uusimpien tutkimusten mukaan uusimmat tutkimukset ovat keskimäärin yhdentekeviä.

Eusa
Seuraa 
Viestejä15632
Liittynyt16.2.2011

Luvut näyttävät olevan jaollisia joko 9:llä tai 11:llä. Strategia sen mukaan...

Hienorakennevakio suoraan vapausasteista: 1 / (1+2¹+3²+5³+1/2¹*3²/5³) = 1 / 137,036

Kingisghan
Seuraa 
Viestejä94
Liittynyt16.1.2016

Tässä malli jolla lasket onnen numerosi, lotossa ainaakin yksi oikein.

Esimerkiksi, jos olet syntynyt 3. tammikuuta 1986, laskisit numerosi näin:

3+1+1+9+8+6= 28

Koska lopputulos on 28, laskisit seuraavaksi yhteen 2 + 8= 10.

Nyt lasketaan yhteen 1+ 0 = 1.

Onnennumero olisi siis 1.

Joka kauvan elää, se paljon näkee.

Eusa
Seuraa 
Viestejä15632
Liittynyt16.2.2011

Eusa kirjoitti:
Luvut näyttävät olevan jaollisia joko 9:llä tai 11:llä. Strategia sen mukaan...

Jaa, on siellä muitakin jaollisuuksia, kuten 101... Anyhow, jaollisuuksia tutkimalla voi optimoida.

Hienorakennevakio suoraan vapausasteista: 1 / (1+2¹+3²+5³+1/2¹*3²/5³) = 1 / 137,036

pöhl
Seuraa 
Viestejä927
Liittynyt19.3.2005

Mietin seuraavaa ideaa. Entä jos vaikka tapauksessa 363 laskisi taulukkoon arvoja muotoa 10^n mod 363 ja m*(10^n-1)/9 mod 363 eri n:n ja m:n arvoilla. Sitten yrittäisi etsiä sellaisen yhdistelmän, että näiden summana saadaan 0 mod 363 ja pidettäisiin huoli, että eri numerot tulevat lukuun peräkkäin. Koska esim 111223=111*1000+22*10+3=((10^3-1)/9)*10^3+2*(10^2-1)/9*10 + 3. Taulukon saisi kyhättyä nopeasti tiettyyn rajaan asti, mutta miten siitä voisi lukea nopeasti oikean yhdistelmän, joka antaa luvun joka on 0 mod 363?

Retromake
Seuraa 
Viestejä48
Liittynyt1.12.2017

pöhl kirjoitti:
Mietin seuraavaa ideaa. Entä jos vaikka tapauksessa 363 laskisi taulukkoon arvoja muotoa 10^n mod 363 ja m*(10^n-1)/9 mod 363 eri n:n ja m:n arvoilla. Sitten yrittäisi etsiä sellaisen yhdistelmän, että näiden summana saadaan 0 mod 363 ja pidettäisiin huoli, että eri numerot tulevat lukuun peräkkäin. Koska esim 111223=111*1000+22*10+3=((10^3-1)/9)*10^3+2*(10^2-1)/9*10 + 3. Taulukon saisi kyhättyä nopeasti tiettyyn rajaan asti, mutta miten siitä voisi lukea nopeasti oikean yhdistelmän, joka antaa luvun joka on 0 mod 363?

Ratkaisusi luultavasti saisi ohjelmointiputkan testeissä täydet pisteet. Suoraviivainen metodi perustuu tietyn pituisten "sileiden" lukujen generoimiseen ja näiden lukujen testaamiseen annettua lukujoukkoa vastaan moduloaritmetiikkaan perustuen. Testasin menetelmäsi ohjelmoimalla C# -kielellä suurin piirtein Python -ratkaisuasi vastaavan metodin. Kielen suurin kokonaislukutietotyyppi 2^64 ei ollut riittävä tähän tehtävään, joten ensin oli asennettava BigInteger-tietotyyppi, joka mahdollistaa laskennan rajattoman pitkillä kokonaisluvuilla. 

Vanhalla henkitoreisella läppärilläni kesti 27 minuuttia laskea kaikkien annettujen 162 luvun nousevat ja laskevat pienimmät sileät luvut. Uusi nykytason kone selviytyisi varmasti tästä alle 3:ssa minuutissa. Pitkä laskenta-aika johtuu tasoitettavien lukujen joukkoon sisältyvistä muutamasta hankalasta tapauksesta, jotka ratkesivat vasta 24-numeroisilla sileillä luvuilla.

Ohjelmasta saisi varmaankin viilattua version, joka laskisi tuloksen sekunneissa. Ohjelmointitehtävissä, joissa annetaan valmis joukko ratkaistavia tapauksia,  on usein mahdollista erilaisilla esiprosessoinneilla virittää ratkaisu, joka on äärimmäisen nopea juuri kyseiseen tehtävään, mutta joka ei välttämättä selviäisi tapauksesta, joka ei sisälly alkuperäiseen tehtävänantoon.

Voihan olla, että joku on onnistunut analyyttisesti kehittämään yleisen funktion, joka laskee mielivaltaiselle kokonaisluvulle pienimmän "sileän" luvun. Oman ideasikin kehittelystä voisi löytyä jotakin. Eusa aiemmin jo mainitsikin apukeinona jaollisuuksien tutkimisen. Lisäksi voisi tarkastella millaista  syklisyyttä lukujen numeropositioissa esiintyy summattaessa lukua toistuvasti itsensä kanssa.

pöhl
Seuraa 
Viestejä927
Liittynyt19.3.2005

Retromake kirjoitti:

Ratkaisusi luultavasti saisi ohjelmointiputkan testeissä täydet pisteet.

Tuosta tehtävästä saa täydet pisteet jos ratkaisee tehtävän optimaalisesti vaikka kone jauhaisi ratkaisua viisi vuotta. Mulla on pyörinyt jo puoli vuotta Python-koodi tämän ratkaisemiseen: https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ssana2

Mutta aika rumalta tuon tasaisten lukujen koodi vaikutti. Tuli vaan ensimmäisenä mieleen kirjoittaa peräkkäiset for-luupit generoimaan tasaiset luvut. Taitaisi rekursio tuottaa siistimmän koodin. Tai ehkä itertoolseista löytyisi jotain sopivaa. Mutta varmaankin nopeampi algoritmi vaatisi toisenlaisen idean. Eulerin lauseestahan saa nopeasti tasaisen luvun, mutta tämä ei ole aina optimaalinen.

Eusa
Seuraa 
Viestejä15632
Liittynyt16.2.2011

Olisiko ihan perinteinen allekkain kertolaskun konstruoiminen ok idea?

Eli katsotaan millä numerolla saadaan loppupäähän pienin / suurin nro tulokseen. Sitten seuraava (kympit) yhtä pieni/suuri tai mahdollisimman lähelle pienempi/suurempi, jne kunnes kaikki tulosluvut on generoitu ja saadaan mahdollisesti kaksi "tasaista lukua"; toinen kerroin antaa laskevan, toinen nousevan numerojärjestyksen. Valitaan pienempi kertoimista.

Tuolla tavoin voisi saada nopeasti edes jonkin tuloksen. Samaa algoritmia noudatten voidaan generoida lähtien hieman suuremmasta/pienemmästä ykkösestä hakemaan löytyisikö pienempiä kertoimia...

Eli ihan peruskouluopein.

Hienorakennevakio suoraan vapausasteista: 1 / (1+2¹+3²+5³+1/2¹*3²/5³) = 1 / 137,036

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat