Sitat av
Dyret
Ny oppgave. Denne er kanskje litt utradisjonell, men den kan være interessant å prøve å forstå.
Kode
int magisk(int i) {
int j = 1337, k = 0;
do k -= i += (i<0) + i;
while (j *= 42);
return k;
}
Denne snutten kan implementeres direkte i nesten hvilket som helst programmeringsspråk, men det er hva den faktisk gjør jeg er interessert i å vite. En C-versjon er lagt ut her:
http://pastebin.com/25z7uGLc så prøv å variere litt på tallet den kalles med og se om dere forstår HVA den gjør og HVORFOR det skjer. Blir det for vanskelig kan vel noen andre poste en ny oppgave etterhvert
du har en du-while løkke, hvo den vil gjøre det som står i do, så lenge while returnerer sant. I de fleste språk vil biten 0 tilsvare False, mens alle andre verier tilsvarer true. Dermed vil denne være sann så lenge J ikke er null, og for hver gang øker verdien til J med en faktor på 42. Siden integere har en "maks-verdi" pga at det er begrenset antall bits som blir allokert til den. Når verdien blir vesentlig stor og den binære formen av tallet tar mer plass enn det som er allokert til en integer oppstår det merkelige situasjoner; som man kan kalle en "overflow". Dette gjør at verdiene til J ikke lenger opptar verdien du ville forventet; rent matematisk. Dette kan være avansert å forklare, men skal forenkle det litt:
Jeg velger å se på en integer som en sirkel: Tenk deg at du har et tau hvor den ene enden er den største negative tallet, og det andre er det største positive tallet, så knytter du endene sammen slik at den største positive verdien er rett ved siden av den største negative verdien. Dette gjør at hvis du skulle passere den største positive verdien, vil du fortsette videre innover på den negative siden av tauet (eller tallrekka). Dette burde egentlig forklares med hvordan binære tall forståes av datamaskinen, men det kan fort bli forvirrende - selv siden jeg ikke er helt 100% stødig med overflow.
J vil derfor hoppe i mellom positive og negative tall helt til den p.g.a. overflow ender med en binær verdi som er lik 0.
For hver av gangene J blir ganget med 42 vil også dette skje:
do k -= i += (i<0) + i;
dette blir en "assigning" av verdier, og skal leses fra høre til venstre. Denne ville og tilsvare følgende kode:
Kode
i += (i<0) + i;
k -= i;
den nederste av de to linjene er ganske intuitiv og senker verdin til K med verdien som i har i det tidspunktet. Utregningen av i kan dog være litt forvirrende. Det er derfor greit å vite hvordan en condition (boolsk verdi) virker. Denne har en av 2 verdier. 1 hvis True, eller 0 hvis false.
Dette betyr at så lenge i er et tall under null vil denne være 0, og for alt annet 1. Dermed kan vi videre igjen skrive denne om til litt mer forstålig kode:
Kode
if (i<0)
i += 1 + i;
else
i += 0 + i;
k -= i;
når løkken er kjørt ferdig, og j tilfeldigvis er blitt 0 (grunner overflow, som forklart over). så vil funksjonen returnere verdien til k.
Ble kanskje litt rotete forklart, men jeg regner med jeg er sporet av svaret? Kan dyret bekrefte dette?
Edit: Vil legge til at grunnen til at en overflow i en integer vil føre til et negativt tall er at det binære tallet 0000000...0 tilsvarer ikke 0, slik mange ville tro; men det "største" negative tallet. Mens 0 vil ha en større binær verdi. For intereserte: les mer om forskjellen mellom signed og unsigned integers.
Legger til et litt bedre forsøk på forklaring av overflowen:
Forklaring på overflow:
Tenk deg at du hadde en 3 bits integer. Denne skal være signed (altså ha mulighet for både negative og positive tall).
Du vet da at du har muligheter fra 000 til 111. (rent oversatt 0 til og med 7). Siden du ønsker å kunne beskrive negative tall sier du at nullpunktet er 3 (eller 011).
Dermed vil du få følgende:
0 = -3
1 = -2
2 = -1
3 = 0
4 = 1
5 = 2
6 = 3
7 = 4
Tenk deg nå at du har tallet 3, og ganger dette med 2. Svaret du får er 6. Største mulige tallet du har i ditt nye system er 6, og du fortsetter derfor videre på andre siden av tallinjen. (6-4=2) så du vil gå 2 hakk videre fra toppen. og 3*2 blir derfor med ditt tallsystem -2. Ganger du dette tallet igjen med 2 får du -4. Dette er og utenfor skalaen og fortsetter på andre siden av skalaen. Du får dermed at (-2*2=4).
Kanskje litt vanskelig å forstå, men håper det ga en liten forklaring for noen.
Ny oppgave: (ikke så veldig vanskelig).
Kode
#include <iostream>
using namespace std;
int A(int b)
{
if (b==1)
return 1;
else
return (b*A(b-1));
}
int main()
{
cout << A(4) << endl;
}
oppgaven over er forresten i C++.
Sist endret av etse; 15. april 2010 kl. 17:09.
)
