{ This is a program to solve problem 3 on questions4, i.e. the problem from the J. of Algorithms on finding the maximum of a[0..n] using a minimum number of questions "is a[i] < k?". } program max(output); type state = array [1..5] of integer; answer = record questions: integer; bestquestion: integer; end; var i: integer; perm: array [-1..5, -1..5] of integer; current: state; table: array [0..252] of answer; { A state is a set of n numbers in the range 0..m, ordered from highest to lowest. The array entry "perm[n,m]" holds the number of possible states for each pair of values n,m. The array is filled in using "perm[n,m] = perm[n-1,m] + perm[n,m-1]". In fact, perm[n,m] is equal to the binomial coefficient (n+m)Cn, so that perm is in fact just pascal's triangle. } procedure initialise; var n,m: integer; begin for n := -1 to 5 do perm[n,-1] := 0; for m := -1 to 5 do perm[-1,m] := 0; for n := 0 to 5 do perm[n,0] := 1; for m := 0 to 5 do perm[0,m] := 1; for n := 1 to 5 do for m := 1 to 5 do perm[n,m] := perm[n-1,m] + perm[n,m-1]; end; { Information about each state is held in an array "table". This routine finds the table entry corresponding to a particular state. } function sequence(x:state): integer; begin sequence := perm[5,x[1]-1] + perm[4,x[2]-1] + perm[3,x[3]-1] + perm[2,x[4]-1] + perm[1,x[5]-1]; end; { This routine does the reverse job - it finds the state corresponding to a sequence number. } procedure findstate(n:integer; var x:state); var i: integer; begin for i := 1 to 5 do begin x[i] := 5; while n < perm[6-i,x[i]-1] do x[i] := x[i] - 1; n := n - perm[6-i,x[i]] end; end; begin initialise; for i := 1 to 5 do current[i] := 5; writeln(sequence(current)); findstate(250,current); for i := 1 to 5 do write(current[i]); writeln; end.