56 lines
1.5 KiB
Text
56 lines
1.5 KiB
Text
' Zeckendorf number representation
|
|
DECLARE FUNCTION ToZeckendorf$ (N%)
|
|
' The maximum Fibonacci number that can fit in a
|
|
' 32 bit number is Fib&(45)
|
|
CONST MAXFIBINDEX% = 45, TRUE% = -1, FALSE% = 0
|
|
DIM SHARED Fib&(1 TO MAXFIBINDEX%)
|
|
Fib&(1) = 1: Fib&(2) = 2
|
|
FOR I% = 3 TO MAXFIBINDEX%
|
|
Fib&(I%) = Fib&(I% - 1) + Fib&(I% - 2)
|
|
NEXT I%
|
|
FOR I% = 0 TO 20
|
|
SixChars$ = SPACE$(6)
|
|
RSET SixChars$ = ToZeckendorf$(I%)
|
|
PRINT USING "### "; I%; : PRINT SixChars$
|
|
NEXT I%
|
|
END
|
|
|
|
FUNCTION ToZeckendorf$ (N%)
|
|
' returns the Zeckendorf representation of N% or "?" if one cannot be found
|
|
IF N% = 0 THEN
|
|
ToZeckendorf$ = "0"
|
|
ELSE
|
|
Result$ = ""
|
|
FPos% = MAXFIBINDEX%
|
|
Rest% = ABS(N%)
|
|
' Find the first non-zero Zeckendorf digit
|
|
WHILE FPos% > 1 AND Rest% < Fib&(FPos%)
|
|
FPos% = FPos% - 1
|
|
WEND
|
|
' If we found a digit, build the representation
|
|
IF FPos% >= 1 THEN ' have a digit
|
|
SkipDigit% = FALSE%
|
|
WHILE FPos% >= 1
|
|
IF Rest% <= 0 THEN
|
|
Result$ = Result$ + "0"
|
|
ELSEIF SkipDigit% THEN ' we used the previous digit
|
|
SkipDigit% = FALSE%
|
|
Result$ = Result$ + "0"
|
|
ELSEIF Rest% < Fib&(FPos%) THEN ' cannot use the digit at FPos%
|
|
SkipDigit% = FALSE%
|
|
Result$ = Result$ + "0"
|
|
ELSE ' can use this digit
|
|
SkipDigit% = TRUE%
|
|
Result$ = Result$ + "1"
|
|
Rest% = Rest% - Fib&(FPos%)
|
|
END IF
|
|
FPos% = FPos% - 1
|
|
WEND
|
|
END IF
|
|
IF Rest% = 0 THEN
|
|
ToZeckendorf$ = Result$
|
|
ELSE
|
|
ToZeckendorf$ = "?"
|
|
END IF
|
|
END IF
|
|
END FUNCTION
|