R-funksjonen

[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.

[Gustav]

Vanlig rekursjon er altfor tregt, så bruker memoisering og Python :

Code: Select all

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?

[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 ^^

[Gustav]

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?

[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.

[Nebuchadnezzar]

Just for fun, matlab. Klarer ikke hente ut listeverdiene men får rett svar. Og det er kanskje det viktigste? :p

Code: Select all

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