Forum Mjukvara Programmering och digitalt skapande Tråd Inlägg

ETt programmeringspuzzel

1
Skriv svar
Permalänk
Medlem
●

ETt programmeringspuzzel

Surfade runt och hittade det här problemet i ett inlägg på lambda-the-ultimate som jag tänkte att någon kanske skulle tycka var kul att fundera över:

Citat:

Your stair-climbing robot has a very simple low-level API: the "step" function takes no argument and attempts to climb one step as a side effect. Unfortunately, sometimes the attempt fails and the robot clumsily falls one step instead. The "step" function detects what happens and returns a boolean flag: true on success, false on failure. Write a function "step_up" that climbs one step up (by repeating "step" attempts if necessary). Assume that the robot is not already at the top of the stairs, and neither does it ever reach the bottom of the stairs. How small can you make "step_up"? Can you avoid using variables (even immutable ones) and numbers?

Inte så jättelurigt kanske, men det finns ett par fällor att akta sig för om roboten är riktigt klumpig

Senast redigerat
Redigera
Citera flera Citera
Permalänk
Medlem
●

Jag tror jag har en lösning, PM:ar så jag inte sabbar för de andra.

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

Kan ge ett litet tips:

tänk rekursivt. funktionen kan skrivas på en rad

Dold text
Redigera
Citera flera Citera
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av ChristofferC
Kan ge ett litet tips:

tänk rekursivt. funktionen kan skrivas på en rad

Dold text

Tänk om roboten är så klumpig att funktionen ger stack overflow?

Dold text
Visa signatur

Blogg. Webboken. Pinboard, Last.fm, Facebook, Kongregate. W3fools.
Validera din HTML, men skryt inte om att du gör det.
Använd HTML5 och kom ihåg semantiken!

Redigera
Citera flera Citera
Permalänk
Medlem ★
●
Citat:

Ursprungligen inskrivet av You

Tänk om roboten är så klumpig att funktionen ger stack overflow?

Dold text

Då är roboten defekt och det spelar ingen roll om det blir stack overflow.

Dold text
Redigera
Citera flera Citera
Permalänk
Medlem
●

Humm, blir en ganska trist tråd om alla PMar mig Bra att ni började med [spoiler.]-taggen istället även om det oxå börjar bli lite onödigt, inte direkt så att man läser hela tråden om man inte är ute efter att se hur andra löst det eller problem man kan få ändå?

You:

Det går utmärkt att skriva en enradare utan stackoverflow om man gör det i ett språk med tailcall-optimering

Dold text
Redigera
Citera flera Citera
Permalänk
Medlem ★
●

Skippar spoiler nu...

Utan rekursion så kan vi inte komma undan en räknare som håller koll på vilket trappsteg vi står på. Med tail call-optimering så måste alltså en räknare introduceras. Can't have your cake and eat it...

Redigera
Citera flera Citera
Permalänk
Medlem
●

Nej, du har givetvis rätt i att någon form av räknare kommer att behövas, men det gäller alla lösningar skulle jag påstå. Misslyckas step 20 ggr i rad, så måste man givetvis hålla rätt på det, antingen genom att ha stackat upp 20 anrop på sin stack som då blivit en form av en räknare, med en vanlig variabel eller på något annat vis.

Eller så drar man gränsen vid vad man faktiskt skriver, och då går det utmärkt att göra det utan variabler och siffror i många språk.

Redigera
Citera flera Citera
1
Skriv svar
Senaste nyheterna
Hårdvara
Mjukvara
Övrigt
Nytt i forumet
Datorkomponenter
System
Ljud, bild och kommunikation
Spel och mjukvara