Side 1 av 1
R-funksjonen
Lagt inn: 21/08-2014 23:41
av Aleks855
I forbindelse med et jobbintervju som gikk bra, ble jeg kalt inn på en teknisk test i dag, der jeg fikk 2 timer på å løse en del programmeringsoppgaver.
Den ene oppgaven lød:
En funksjon $R(n)$ er definert slik at $R(n) = R(n-R(n-1)) + R(n-R(n-2))$
$R(1) = 1, R(2) = 1$
Implementer funksjonen og regn ut $R(77)$.
Jeg måtte gjøre det i Java, men for all del, bruk hva du vil.
Re: R-funksjonen
Lagt inn: 22/08-2014 01:57
av Gustav
Vanlig rekursjon er altfor tregt, så bruker memoisering og Python :
Kode: Velg alt
function_values = {}
#Velger startbetingelser R(0)=R(1)=1
function_values[0] = 1
function_values[1] = 1
def R(n):
if not n in function_values:
function_values[n] = R(n-R(n-1))+R(n-R(n-2))
return function_values[n]
print R(77)
#40
Hvordan gjorde du det?
Re: R-funksjonen
Lagt inn: 22/08-2014 10:41
av Aleks855
Ser jeg glemte å nevne at startbetingelsene er $R(1) = 1, R(2) = 1$. Siden du starta indekseringa på 0 så tror jeg du fant R(76).
Jeg tenkte i samme baner som deg. Jeg prøvde først med vanlig rekursjon, men den viste ingen tegn på å bli ferdig (som sannsynligvis var hele poenget), så jeg lagra ei liste over resultatene, der liste-indeksen svarer til indeksen i følgen. Svaret var ganske åpenbart da den printa det ^^
Re: R-funksjonen
Lagt inn: 22/08-2014 11:50
av Gustav
Aleks855 skrev:Ser jeg glemte å nevne at startbetingelsene er $R(1) = 1, R(2) = 1$. Siden du starta indekseringa på 0 så tror jeg du fant R(76).
Jeg tenkte i samme baner som deg. Jeg prøvde først med vanlig rekursjon, men den viste ingen tegn på å bli ferdig (som sannsynligvis var hele poenget), så jeg lagra ei liste over resultatene, der liste-indeksen svarer til indeksen i følgen. Svaret var ganske åpenbart da den printa det ^^
Ok, med de nye startbetingelsene blir svaret mitt 42. Eneste forskjellen i løsningene er at jeg har brukt en dictionary istedenfor liste.
En veldig enkel oppgave dersom man har drevet litt med project euler:)
Fikk du noen andre artige oppgaver?
Re: R-funksjonen
Lagt inn: 22/08-2014 12:13
av Aleks855
42 stemmer ja
De andre oppgavene var mer programmeringstekniske. Under "easy" var FizzBuzz-problemet, som jeg vil si er helt trivielt for de aller fleste. Resten var kun myntet på objektorientert programmering og database-spørringer.
Re: R-funksjonen
Lagt inn: 22/08-2014 13:39
av Nebuchadnezzar
Just for fun, matlab. Klarer ikke hente ut listeverdiene men får rett svar. Og det er kanskje det viktigste? :p
Kode: Velg alt
function [ n ] = R( n )
if exist('functionList','var')==0
global functionList;
functionList(1:2,1)=1;
end
if n <= length(functionList)
n = functionList(n);
else
n = R(n-R(n-1)) + R(n-R(n-2));
functionList(end+1,1) = n;
end