IT ØVING 10

[Nebuchadnezzar]

Tenker å kanskje lage en liten tråd for hver slik øving. Jeg

http://itgk.idi.ntnu.no/oving/oving10-matlab.pdf

Oppgave 3 - Rekursjon

a) Skriv en rekursiv funksjon som regner ut summen av alle tall fra 1 til n, hvor n er gitt som et
parameter.

Selvølgelig kunne jeg tatt en frekkis og skrevet

Code: Select all

function Y = Sum(N)

Y = sum(1:N)    

end    

eller

Code: Select all

function Y = Sum(N)

Y = (n*(n+1))/2;  

end
    

Men dette er jo ikke lov. Er koden under derimot lovlig ?

Code: Select all

function Y = sumtall(N)

p = 0;
i = 0;
    while i < N
         i = i + 1;
         p = p + i;
    end

Y = p;

end

Og er koden underen god metode å løse oppgave 2 på? Burde være lett^^

Oppgave 2 a)

Code: Select all

k = randi(10^4,10^3,1);

fid = fopen('random.txt','wt');  
fprintf(fid,'%f\n',k);  
fclose(fid);

Oppgave 2 b)

Code: Select all

function Y = Laveste( N )

a = load('random.txt');
Y = zeros(N,1);

for i=1:N
    Y(i,1)=min(a);
    p=find(a==min(a));
    a(p)=[];
end

Y;

end

Oppgave 2 c)

Code: Select all

function T = Hoyeste( N )

a = load('random.txt');
K = zeros(N,1);

for i=1:N
    K(i,1)=max(a);
    p=(a==max(a));
    a(p)=[];
end

T = (sum(K)/sum(a))*100;

end 

[Vektormannen]

En rekursiv funksjon skal kalle seg selv i stedet for å iterere gjennom en løkke.

Jeg ville gjort noe sånt som

Code: Select all

function Y = Sum(N)
if (N == 0)
    Y = 0;
else
    Y = N + Sum(N-1);
end
end

[Nebuchadnezzar]

Takker. Da forstår jeg det og. Nå "sliter" jeg med en annen oppgave og

Oppgave 4 - Binærsøk
I binærsøk bruker man prinsippet om å dele en sortert liste i to helt til man finner elementet man leter
etter.
a) Implementer binærsøk med løkker.
b) Implementer binærsøk med rekursjon.

Prøvde meg med noe slikt som dette.

Code: Select all

function Y = finnLokker( N )

a = (1:50);

b = numel(a);
c = floor(b/2);

if N>a(b) || N<a(1)
    Y = 0;
    return
end

    while a(1)>0

        if N > a(c)
            a(1:c)=[];
        elseif N < a(c)
            a(c:b)=[];
        else
           Y = 1;
          return
        end
        
      
b = numel(a);
c = floor(b/2);

    end
    Y = 0;
end

Trenger vel egentlig ikke si det, men koden fungerer ikke :p

For de fleste verdier gir den ut riktig. Men for noen tall, slik som 11, 17 bare krasjer programmmet... Noen som kan hjelpe ? =)

[Nebuchadnezzar]

prøvde også å lage en funksjon som gav rett deling av tall. GUD DET BLE KOMPLISERT. I det minste for lille uskyldige meg...

Altså skriver jeg inn for eksempel 1000 skal funksjonen retunere 1000
eksempelvis under. Input og output

Code: Select all

1       =         1
10      =        10
100     =       100
1000    =      1000
12345   =    12 345
123456  =   123 456
1234567 = 1 234 567

Koden min under, som abre nesten fungerer. Funker fint for 1/3 av alle tallene. Alle tall med multiplisitet 7 fungerer ikke

Code: Select all

function Y = printMedMellomrom(a)

b=num2str(a);
c=length(b);
i=1;
p=2;
j=0

if round(a)~=a
    return
    
elseif c<5
    Y=b;
    return
    
end

if mod(c-5,3)==0
r=1;
t=0;
elseif mod(c-6,3)==0
r=0;
t=0; 
else mod(c-7,3)==0
r=2;
t=1;
end

k(1)=floor(a/10^(c-2-i+r));
i = i + 3;
    while i < length(b) + t
       j = k(p-1)*10^(c-2-i+3+r) + j 
       h = (a - j);
     k(p)= floor(h/10^(c-2-i+r));
     
i = i + 3;
p = p + 1;
    
    end
    Y = k;
    return
    
end

Fungerer som sagt bare nesten. Alle tall med multiplisitet 7, der glemmer funksjonen og ta med de tre siste desimalene...

EDIT: La til en frekk friskus der jeg bare legger til t. Dette fikser problemet med multiplisitet 7. Derimot fungerer ikke funksjonen min for store tall hva gjør jeg?

[Nebuchadnezzar]

NY KODE

Code: Select all

function Y = sistesiffer(a)

c = length(num2str(a));

i = 0;
p = 1;

if mod(c-5,3)==0
r=2
elseif mod(c-6,3)==0
r=3;
else mod(c-7,3)==0
r=1;
end

k(1)=(a - mod(a,10^(c-r)))/(10^(c-r))

while i < c
    k(p) = (mod(a,10^(c-i+3-r)) - mod(a,10^(c-r-i)))/(10^(c-r-i));
    
    i = i + 3;
    p = p + 1;
end

Y = k;

end

Kanskje litt mer effektiv, bedre? Uansett tror denne skal funke, men streiker fortsatt for store tall. Noen tips til forbedringer?

[drgz]

Takker. Da forstår jeg det og. Nå "sliter" jeg med en annen oppgave og

Oppgave 4 - Binærsøk
I binærsøk bruker man prinsippet om å dele en sortert liste i to helt til man finner elementet man leter
etter.
a) Implementer binærsøk med løkker.
b) Implementer binærsøk med rekursjon.

Prøvde meg med noe slikt som dette.

Code: Select all

function Y = finnLokker( N )

a = (1:50);

b = numel(a);
c = floor(b/2);

if N>a(b) || N<a(1)
    Y = 0;
    return
end

    while a(1)>0

        if N > a(c)
            a(1:c)=[];
        elseif N < a(c)
            a(c:b)=[];
        else
           Y = 1;
          return
        end
        
      
b = numel(a);
c = floor(b/2);

    end
    Y = 0;
end

Trenger vel egentlig ikke si det, men koden fungerer ikke :p

For de fleste verdier gir den ut riktig. Men for noen tall, slik som 11, 17 bare krasjer programmmet... Noen som kan hjelpe ? =)

Code: Select all

function idx = binloop(x,k)
if ~issorted(x)
    x = sort(x);
end
N = length(x);

minv = 1;
maxv = N;

while minv <= maxv
    mid = round((minv+maxv)/2);
    if k < x(mid)
        maxv = mid;
    elseif k > x(mid)
        minv = mid;
    else
        idx = mid;
        break;
    end
    if minv == (maxv-1)
        break;
    end
end
end

for binærsøk med løkker. Kan nok legge til flere sjekker så den blir mer robust, men fungerer i utgangspunktet for (unikt) sortert input.

Code: Select all

function idx = binrec(x,k,minv,maxv)
if maxv < minv
    idx = 0;
    return
end
mid = round((minv+maxv)/2);
if x(mid) == k
    idx = mid;
    return;
elseif x(mid) > k
    idx = binrec(x,k,minv,maxv-1);
else
    idx = binrec(x,k,minv+1,maxv);
end
end

for binærsøk med rekursjon.

Ellers lurer jeg på hvor du henter algoritmene dine fra? Ser ut som at du gjør oppgaven til noe mye vanskeligere enn det den er. Jeg ville jo tro at læreboka/noe annet i pensum har pseudokoden for algoritmen, og da er det som regel kun å prøve å omformulere til et programmeringsspråk.

[Nebuchadnezzar]

Skriver mest ut av rumpen ja. Har litt restriksjoner mpt å lese meg opp på masse. vil helst finne ut av ting selv. men skal nok lese meg opp litt ja. Var litt vanskelig å gjøre dette før man har lest noe særlig. Selv syntes jeg at koden min fungerer nesten, og det er jo kanskje bra? Føler at om jeg bare bruker masse avanserte funksjoner, og bare skriver av lærer jeg fint lite. -Stanger jeg derimot hodet mot veggen, og prøver selv først så forstår jeg mer (kanskje)

[drgz]

prøvde også å lage en funksjon som gav rett deling av tall. GUD DET BLE KOMPLISERT. I det minste for lille uskyldige meg...

Altså skriver jeg inn for eksempel 1000 skal funksjonen retunere 1000
eksempelvis under. Input og output

Code: Select all

function printMedMellomrom(N)

Nstr = num2str(N);
nstr = [];

for k = 0:length(Nstr)-1;
    if ~mod(k,3)
        nstr = [Nstr(end-k) ' ' nstr];
    else
        nstr = [Nstr(end-k) nstr];
    end
end

nstr

[drgz]

Skriver mest ut av rumpen ja. Har litt restriksjoner mpt å lese meg opp på masse. vil helst finne ut av ting selv. men skal nok lese meg opp litt ja. Var litt vanskelig å gjøre dette før man har lest noe særlig.

Det er greit å finne ut av ting selv, men du bør ha en plan. Har du f.eks kladdet litt og sett hvordan du vil at algoritmen skal løse problemet ditt?

Selv syntes jeg at koden min fungerer nesten, og det er jo kanskje bra?

Nesten holder aldri når du blir bedt om å skrive en kode som løser et gitt problem. Det holder f.eks ikke at du nesten klarer å beregne hva slags maksvekt en bro mellom A og B klarer hvis det skal kjøre ti tusen folk over brua hver dag i rushen.

Føler at om jeg bare bruker masse avanserte funksjoner, og bare skriver av lærer jeg fint lite. -Stanger jeg derimot hodet mot veggen, og prøver selv først så forstår jeg mer (kanskje)

Du kommer mye lenger ved å lese deg opp litt først. Hvis du tror at du klarer å løse alt på strak arm uten å sjekke opp med litteratur så tror jeg du har for høye tanker om deg selv. Dvs. hadde du lest litt om binærsøk på forhånd så hadde du hatt en strategi og visst hvordan du skulle teste koden for å se om den løste problemet eller ei. Slik du har skrevet koden din så er det vanskelig å si hva du egentlig har tenkt.

[Nebuchadnezzar]

Har faktisk to ark fulle med kladd. Der jeg testet koden for hånd. Også kjørt igjennom koden flere ganger, fjerne kolonn og liknende for å se hvor feilen lå. Antakeligvis litt vanskelig å lese koden ja...

Slik jeg tenkte på oppgaven med å dele ett tall med tanke på plassering:

1. Alle tall som er under 10000 skal bare skrives ut

2. Første tall etter dette har 5 siffer og skal ha to plasser før en begynner å tredele. Altså 12 435 for eksempel.

3. Neste tall har 6 desimaler. skal deles først etter 3. 123 432 eksempelvis.

4. Neste tall etter dette har 7 desimaler, og skal hoppe 1 plass før tredeling. Altså 1 234 123

5. Alle tall etter dette vil falle i en av kategoriene ovenfor. Dermed sjekker jeg via mod, hvilke katigori et tall havner i. Så velger jeg hvor en skal begynne å hoppe. For eksempel mod(c-5,3)==0. Vil gi meg at alle tall som kan skrives på formen 5+3k, havner i denne kategorien.

6. mod(k,10^c) gir de n siste sifferene i et tall. Ved bruk av dette, og litt matematikk, så kommer en frem til at for å finne de første sifferene kan en bruke.

(a - mod(a,10^(c-r)))/(10^(c-r));

7. Så bare looper jeg en slik sekvens...

Code: Select all

function Y = sistesiffer(a)

c = length(num2str(a));

if floor(a)~=ceil(a)
    return
elseif a<0
    z = -1;
    a = -a;
    c = c-1;
elseif c<5
    Y = a;
    return
else
    z = 1;
end

i = 0;
p = 1;

if mod(c-5,3)==0
r=2;
elseif mod(c-6,3)==0
r=3;
elseif mod(c-7,3)==0
r=1;
else
    return
end

k(1)=(a - mod(a,10^(c-r)))/(10^(c-r));

while i < c
    k(p) = (mod(a,10^(c-i+3-r)) - mod(a,10^(c-r-i)))/(10^(c-r-i));
    
    i = i + 3;
    p = p + 1;
end
k(1)=z.*k(1)
Y = k;

end

Dog har jeg lært en del av dette, om enn ikke å skrive god kode...

1. Ikke skriv midt på natten.
2. Psudokode først, alltid.
3. Stygg kode = det kan alltid gjøres bedre (på it øvinger)
4. Lært meg hvordan søke igjennom kode for feil.
5. Lært meg å bruke rekrusjon
6. Lært at ClaudeShannon er en engel