[PSEUDOCODICE] Suggerimento: un qualsiasi algoritmo ricorsivo

[birmarco]

Ciao a tutti!

Devo fare delle prove di programmazione con il linguaggio macchina, più nello specifico devo implementare delle funzioni ricorsive, e avrei bisogno qualche di qualche esempio di algoritmo ricorsivo facilmente implementabile in linguaggio macchina. Quindi deve operare su interi e non deve essere troppo lungo. L'utilità è relativa in quanto devo solo fare un po' di esercizi, se ce l'ha tanto meglio così almeno faccio qualcosa di sensato Mi basta anche solo il nome dell'algoritmo e me lo cerco io, se mi postate direttamente il codice va bene pseudocodice, ANSI C, Visual Basic .Net e non .Net, Java...

Grazie!

[GByTe87]

Il classico fattoriale?

[birmarco]

Originariamente inviato da GByTe87

Il classico fattoriale?

Grazie! Non ci avevo pensato!

[gugoXX]

Fibonacci?
Fatto bene e' un po' meno banale.

[british]

Sempre in stile fattoriale, calcolare la n-esima potenza di un naturale.
Salendo di complessità, l'algoritmo di Euclide; oppure la ricerca binaria.

ciao!

[banryu79]

Calcolare la sequenza di Collatz (Collatz problem) di un numero naturale.

[birmarco]

Grazie dei suggermenti!

Originariamente inviato da banryu79

Calcolare la sequenza di Collatz (Collatz problem) di un numero naturale.

Non ho capito bene cosa fa quest'algoritmo... è un po' come il calcolo dei decimali del pi greco con iil PC?

[banryu79]

Originariamente inviato da birmarco

Non ho capito bene cosa fa quest'algoritmo... è un po' come il calcolo dei decimali del pi greco con iil PC?

Please, click here -> Let me Google that for you, you lazy!

Le prime due entry dovrebbero essere ampiamente sufficienti.
Altrimenti eccoti l'algoritmo in Haskell; l'input è un numero naturale, l'output una lista di numeri naturali:

-- computes the Collatz sequence for the given integral
collatz :: (Integral a) => a -> [a]
collatz n
    | n <= 0    = error "zero or negative number"
    | n == 1    = [1]
    | even n    = n : collatz (n `div` 2)
    | otherwise = n : collatz (3*n + 1)

Esempi di esecuzione:

"ghci>" collatz 1
[1]

"ghci>" collatz 5
[5,16,8,4,2,1]

"ghci>" collatz 10
[10,5,16,8,4,2,1]

"ghci>" collatz 100
[100,50,25,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

In pratica: prendi un numero naturale N. Se N è pari, dividilo per due, se N è dispari moltiplicalo per 3 e aggiungi 1. Ripeti questa sequenza di operazioni finche non ottieni come risultato 1 (e qui ti fermi). La congettura (Collatz conjecture) è che non importa con quale numero naturale si parta: alla fine si arriva sempre a 1:

"ghci>" collatz 1000
[1000,500,250,125,376,188,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
 
"ghci>" collatz 1234567890
[1234567890,617283945,1851851836,925925918,462962959,1388888878,694444439,2083333318,1041666659,3124999978,1562499989,4687499968,2343749984,1171874992,585937496,292968748,146484374,73242187,219726562,109863281,329589844,164794922,82397461,247192384,123596192,61798096,30899048,15449524,7724762,3862381,11587144,5793572,2896786,1448393,4345180,2172590,1086295,3258886,1629443,4888330,2444165,7332496,3666248,1833124,916562,458281,1374844,687422,343711,1031134,515567,1546702,773351,2320054,1160027,3480082,1740041,5220124,2610062,1305031,3915094,1957547,5872642,2936321,8808964,4404482,2202241,6606724,3303362,1651681,4955044,2477522,1238761,3716284,1858142,929071,2787214,1393607,4180822,2090411,6271234,3135617,9406852,4703426,2351713,7055140,3527570,1763785,5291356,2645678,1322839,3968518,1984259,5952778,2976389,8929168,4464584,2232292,1116146,558073,1674220,837110,418555,1255666,627833,1883500,941750,470875,1412626,706313,2118940,1059470,529735,1589206,794603,2383810,1191905,3575716,1787858,893929,2681788,1340894,670447,2011342,1005671,3017014,1508507,4525522,2262761,6788284,3394142,1697071,5091214,2545607,7636822,3818411,11455234,5727617,17182852,8591426,4295713,12887140,6443570,3221785,9665356,4832678,2416339,7249018,3624509,10873528,5436764,2718382,1359191,4077574,2038787,6116362,3058181,9174544,4587272,2293636,1146818,573409,1720228,860114,430057,1290172,645086,322543,967630,483815,1451446,725723,2177170,1088585,3265756,1632878,816439,2449318,1224659,3673978,1836989,5510968,2755484,1377742,688871,2066614,1033307,3099922,1549961,4649884,2324942,1162471,3487414,1743707,5231122,2615561,7846684,3923342,1961671,5885014,2942507,8827522,4413761,13241284,6620642,3310321,9930964,4965482,2482741,7448224,3724112,1862056,931028,465514,232757,698272,349136,174568,87284,43642,21821,65464,32732,16366,8183,24550,12275,36826,18413,55240,27620,13810,6905,20716,10358,5179,15538,7769,23308,11654,5827,17482,8741,26224,13112,6556,3278,1639,4918,2459,7378,3689,11068,5534,2767,8302,4151,12454,6227,18682,9341,28024,14012,7006,3503,10510,5255,15766,7883,23650,11825,35476,17738,8869,26608,13304,6652,3326,1663,4990,2495,7486,3743,11230,5615,16846,8423,25270,12635,37906,18953,56860,28430,14215,42646,21323,63970,31985,95956,47978,23989,71968,35984,17992,8996,4498,2249,6748,3374,1687,5062,2531,7594,3797,11392,5696,2848,1424,712,356,178,89,268,134,67,202,101,304,152,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
"ghci>"

[birmarco]

Originariamente inviato da banryu79

Please, click here -> Let me Google that for you, you lazy!

Le prime due entry dovrebbero essere ampiamente sufficienti.
Altrimenti eccoti l'algoritmo in Haskell; l'input è un numero naturale, l'output una lista di numeri naturali:

-- computes the Collatz sequence for the given integral
collatz :: (Integral a) => a -> [a]
collatz n
    | n <= 0    = error "zero or negative number"
    | n == 1    = [1]
    | even n    = n : collatz (n `div` 2)
    | otherwise = n : collatz (3*n + 1)

Esempi di esecuzione:


In pratica: prendi un numero naturale N. Se N è pari, dividilo per due, se N è dispari moltiplicalo per 3 e aggiungi 1. Ripeti questa sequenza di operazioni finche non ottieni come risultato 1 (e qui ti fermi). La congettura (Collatz conjecture) è che non importa con quale numero naturale si parta: alla fine si arriva sempre a 1:

"ghci>" collatz 1000
[1000,500,250,125,376,188,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
 
"ghci>" collatz 1234567890
[1234567890,617283945,1851851836,925925918,462962959,1388888878,694444439,2083333318,1041666659,3124999978,1562499989,4687499968,2343749984,1171874992,585937496,292968748,146484374,73242187,219726562,109863281,329589844,164794922,82397461,247192384,123596192,61798096,30899048,15449524,7724762,3862381,11587144,5793572,2896786,1448393,4345180,2172590,1086295,3258886,1629443,4888330,2444165,7332496,3666248,1833124,916562,458281,1374844,687422,343711,1031134,515567,1546702,773351,2320054,1160027,3480082,1740041,5220124,2610062,1305031,3915094,1957547,5872642,2936321,8808964,4404482,2202241,6606724,3303362,1651681,4955044,2477522,1238761,3716284,1858142,929071,2787214,1393607,4180822,2090411,6271234,3135617,9406852,4703426,2351713,7055140,3527570,1763785,5291356,2645678,1322839,3968518,1984259,5952778,2976389,8929168,4464584,2232292,1116146,558073,1674220,837110,418555,1255666,627833,1883500,941750,470875,1412626,706313,2118940,1059470,529735,1589206,794603,2383810,1191905,3575716,1787858,893929,2681788,1340894,670447,2011342,1005671,3017014,1508507,4525522,2262761,6788284,3394142,1697071,5091214,2545607,7636822,3818411,11455234,5727617,17182852,8591426,4295713,12887140,6443570,3221785,9665356,4832678,2416339,7249018,3624509,10873528,5436764,2718382,1359191,4077574,2038787,6116362,3058181,9174544,4587272,2293636,1146818,573409,1720228,860114,430057,1290172,645086,322543,967630,483815,1451446,725723,2177170,1088585,3265756,1632878,816439,2449318,1224659,3673978,1836989,5510968,2755484,1377742,688871,2066614,1033307,3099922,1549961,4649884,2324942,1162471,3487414,1743707,5231122,2615561,7846684,3923342,1961671,5885014,2942507,8827522,4413761,13241284,6620642,3310321,9930964,4965482,2482741,7448224,3724112,1862056,931028,465514,232757,698272,349136,174568,87284,43642,21821,65464,32732,16366,8183,24550,12275,36826,18413,55240,27620,13810,6905,20716,10358,5179,15538,7769,23308,11654,5827,17482,8741,26224,13112,6556,3278,1639,4918,2459,7378,3689,11068,5534,2767,8302,4151,12454,6227,18682,9341,28024,14012,7006,3503,10510,5255,15766,7883,23650,11825,35476,17738,8869,26608,13304,6652,3326,1663,4990,2495,7486,3743,11230,5615,16846,8423,25270,12635,37906,18953,56860,28430,14215,42646,21323,63970,31985,95956,47978,23989,71968,35984,17992,8996,4498,2249,6748,3374,1687,5062,2531,7594,3797,11392,5696,2848,1424,712,356,178,89,268,134,67,202,101,304,152,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
"ghci>"

Più o meno qui avevo capito O forse no? Però ho letto anche che è un problema irrisolto quindi il PC va avanti a calcolare finchè non trova il numero che risolve la congettura, fin'ora irrisolta.
Quindi se scrivo un codice di quel tipo praticamente mi andrà avanti all'infinito giusto? Un po' come il calcolo di tutte le cifre del pi greco...

[banryu79]

Originariamente inviato da birmarco

Più o meno qui avevo capito O forse no?

Ti rispondo quotando questo passaggio:

The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.

That smallest i such that ai = 1 is called the total stopping time of n.[8] The conjecture asserts that every n has a well-defined total stopping time. If, for some n, such an i doesn't exist, we say that n has infinite total stopping time and the conjecture is false.

If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence which does not contain 1. Such a sequence might enter a repeating cycle that excludes 1, or increase without bound. No such sequence has been found.

La congettura è una cosa, un'ipotesi. L'algoritmo per calcolare la sequenza di Collatz di un numero naturale un'altra. L'una non ti vieta di realizzare l'altro. Poi il fatto che la congettura fin'ora abbia retto perchè non si è ancora trovato un numero naturale che la renda falsa, dovrebbe tranquillizarti. In ogni caso ciò non ti impedisce di scrivere l'algoritmo, e quindi di fare esercizio... non so se mi spiego.

Originariamente inviato da birmarco

Però ho letto anche che è un problema irrisolto quindi il PC va avanti a calcolare finchè non trova il numero che risolve la congettura, fin'ora irrisolta.
Quindi se scrivo un codice di quel tipo praticamente mi andrà avanti all'infinito giusto? Un po' come il calcolo di tutte le cifre del pi greco...

C'è un fraintendimento: l'algoritmo che ti ho proposto non dimostra la congettura (ovviamente ), semplicemente calcola la sequenza di Collatz dato qualsiasi numero naturale in input.