Rosetta Code

Zeckendorf number representation: Difference between revisions

Page Discussion

Zeckendorf number representation (view source)

Revision as of 13:29, 17 February 2024

10,135 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
(Dialects of BASIC moved to the BASIC section.)
m (→‎{{header|Wren}}: Minor tidy)
 
(15 intermediate revisions by 9 users not shown)
Line 961:
19 101001
20 101010</pre>
 
==={{header|QuickBASIC}}===
{{trans|ALGOL 68}}
<syntaxhighlight lang="qbasic">
' 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
</syntaxhighlight>
{{out}}
<pre>
0 0
1 1
2 10
3 100
4 101
5 1000
6 1001
7 1010
8 10000
9 10001
10 10010
11 10100
12 10101
13 100000
14 100001
15 100010
16 100100
17 100101
18 101000
19 101001
20 101010
</pre>
 
==={{header|Sinclair ZX81 BASIC}}===
Line 1,191 ⟶ 1,276:
Zeckendorf(20)
</syntaxhighlight>
 
=={{header|bc}}==
<syntaxhighlight lang="bc">obase = 2
f[0] = 1
f[t = 1] = 2
 
define z(n) {
auto p, r
 
for (p = t; p >= 0; --p) {
r += r
if (n >= f[p]) {
r += 1
n -= f[p]
}
}
return(r)
}
 
for (x = 0; x != 21; ++x) {
if (x > f[t]) {
t += 1
f[t] = f[t - 2] + f[t - 1]
}
z(x)
}</syntaxhighlight>
{{out}}
<pre>0
1
10
100
101
1000
1001
1010
10000
10001
10010
10100
10101
100000
100001
100010
100100
100101
101000
101001
101010</pre>
 
=={{header|Befunge}}==
Line 1,863 ⟶ 1,996:
writefln("%2d: %6s", i, i.zeckendorf);
}</syntaxhighlight>
 
=={{header|Dart}}==
{{trans|Java}}
<syntaxhighlight lang="Dart">
class Zeckendorf {
static String getZeckendorf(int n) {
if (n == 0) {
return "0";
}
List<int> fibNumbers = [1];
int nextFib = 2;
while (nextFib <= n) {
fibNumbers.add(nextFib);
nextFib += fibNumbers[fibNumbers.length - 2];
}
StringBuffer sb = StringBuffer();
for (int i = fibNumbers.length - 1; i >= 0; i--) {
int fibNumber = fibNumbers[i];
sb.write((fibNumber <= n) ? "1" : "0");
if (fibNumber <= n) {
n -= fibNumber;
}
}
return sb.toString();
}
 
static void main() {
for (int i = 0; i <= 20; i++) {
print("Z($i)=${getZeckendorf(i)}");
}
}
}
 
void main() {
Zeckendorf.main();
}
</syntaxhighlight>
{{out}}
<pre>
Z(0)=0
Z(1)=1
Z(2)=10
Z(3)=100
Z(4)=101
Z(5)=1000
Z(6)=1001
Z(7)=1010
Z(8)=10000
Z(9)=10001
Z(10)=10010
Z(11)=10100
Z(12)=10101
Z(13)=100000
Z(14)=100001
Z(15)=100010
Z(16)=100100
Z(17)=100101
Z(18)=101000
Z(19)=101001
Z(20)=101010
 
</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
 
const FibNums: array [0..21] of integer =
(1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584,
4181, 6765, 10946, 17711, 28657);
 
 
function GetZeckNumber(N: integer): string;
{Returns Zeckendorf number for N as string}
var I: integer;
begin
Result:='';
{Subtract Fibonacci numbers from N}
for I:=High(FibNums) downto 0 do
if (N-FibNums[I])>=0 then
begin
Result:=Result+'1';
N:=N-FibNums[I];
end
else if Length(Result)>0 then Result:=Result+'0';
if Result='' then Result:='0';
end;
 
 
procedure ShowZeckendorfNumbers(Memo: TMemo);
var I: integer;
var S: string;
begin
S:='';
for I:=0 to 20 do
begin
Memo.Lines.Add(IntToStr(I)+': '+GetZeckNumber(I));
end;
end;
 
 
</syntaxhighlight>
{{out}}
<pre>
0: 0
1: 1
2: 10
3: 100
4: 101
5: 1000
6: 1001
7: 1010
8: 10000
9: 10001
10: 10010
11: 10100
12: 10101
13: 100000
14: 100001
15: 100010
16: 100100
17: 100101
18: 101000
19: 101001
20: 101010
 
Elapsed Time: 26.683 ms.
 
</pre>
 
 
=={{header|EasyLang}}==
{{trans|FreeBASIC}}
<syntaxhighlight>
proc mkfibs n . fib[] .
fib[] = [ ]
last = 1
current = 1
while current <= n
fib[] &= current
nxt = last + current
last = current
current = nxt
.
.
func$ zeckendorf n .
mkfibs n fib[]
for pos = len fib[] downto 1
if n >= fib[pos]
zeck$ &= "1"
n -= fib[pos]
else
zeck$ &= "0"
.
.
if zeck$ = ""
return "0"
.
return zeck$
.
for n = 0 to 20
print " " & n & " " & zeckendorf n
.
</syntaxhighlight>
 
=={{header|EchoLisp}}==
Line 1,908 ⟶ 2,209:
=={{header|Elena}}==
{{trans|C#}}
ELENA 46.x :
<syntaxhighlight lang="elena">import system'routines;
import system'collections;
Line 1,937 ⟶ 2,238:
while (currentFibonaciNum <= num)
{
fibonacciNumbers.append:(currentFibonaciNum);
fibPosition := fibPosition + 1;
Line 1,946 ⟶ 2,247:
int temp := num;
fibonacciNumbers.sequenceReverse().forEach::(item)
{
if (item <= temp)
Line 1,965 ⟶ 2,266:
public program()
{
for(int i := 1,; i <= 20,; i += 1)
{
console.printFormatted("{0} : {1}",i,i.zeckendorf()).writeLine()
Line 2,052 ⟶ 2,353:
for i <- 0..20, do: IO.puts "#{i}: #{Zeckendorf.number(i)}"</syntaxhighlight>
same output
 
 
=={{header|Erlang}}==
{{trans|Elixir}}
<syntaxhighlight lang="Erlang">
% Function to generate a list of the first N Zeckendorf numbers
number(N) ->
number_helper(N, 0, 0, []).
 
number_helper(0, _, _, Acc) ->
lists:reverse(Acc);
number_helper(N, Curr, Index, Acc) ->
case zn_loop(Curr) of
{Bin, Next} ->
number_helper(N - 1, Next, Index + 1, [{Bin, Index} | Acc])
end.
 
% Helper function to find the next Zeckendorf number
zn_loop(N) ->
Bin = my_integer_to_binary(N),
case re:run(Bin, "11", [{capture, none}]) of
match ->
zn_loop(N + 1);
nomatch ->
{Bin, N + 1}
end.
 
% Convert an integer to its binary representation as a string
my_integer_to_binary(N) ->
lists:flatten(io_lib:format("~.2B", [N])).
 
% Test function to output the first 21 Zeckendorf numbers
main([]) ->
ZnNumbers = number(21),
lists:foreach(
fun({Zn, I}) ->
io:format("~p: ~s~n", [I, Zn])
end, ZnNumbers).
</syntaxhighlight>
{{out}}
<pre>
0: 0
1: 1
2: 10
3: 100
4: 101
5: 1000
6: 1001
7: 1010
8: 10000
9: 10001
10: 10010
11: 10100
12: 10101
13: 100000
14: 100001
15: 100010
16: 100100
17: 100101
18: 101000
19: 101001
20: 101010
 
</pre>
 
=={{header|F_Sharp|F#}}==
Line 3,265 ⟶ 3,630:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">zeckendorf[0] = 0;
ZeckendorfRepresentation[0] = 0;
zeckendorf[n_Integer] :=
 
10^(# - 1) + zeckendorf[n - Fibonacci[# + 1]] &@
ZeckendorfRepresentation[n_Integer?Positive]:=
LengthWhile[
NumberDecompose[n, Reverse@Fibonacci@Range[2,1000]] // FromDigits
Fibonacci /@
 
Range[2, Ceiling@Log[GoldenRatio, n Sqrt@5]], # <= n &];
zeckendorfZeckendorfRepresentation /@ Range[0, 20]</syntaxhighlight>
{{Out}}
<pre>{0, 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100,
10101, 100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010}</pre>
 
=={{header|MATLAB}}==
{{trans|Julia}}
<syntaxhighlight lang="MATLAB">
clear all; close all; clc;
 
% Print the sequence for numbers from 0 to 20
for x = 0:20
zeckString = arrayfun(@num2str, zeck(x), 'UniformOutput', false);
zeckString = strjoin(zeckString, '');
fprintf("%d : %s\n", x, zeckString);
end
 
function dig = zeck(n)
if n <= 0
dig = 0;
return;
end
fib = [1, 2];
while fib(end) < n
fib(end + 1) = sum(fib(end-1:end));
end
fib = fliplr(fib); % Reverse the order of Fibonacci numbers
dig = [];
for i = 1:length(fib)
if fib(i) <= n
dig(end + 1) = 1;
n = n - fib(i);
else
dig(end + 1) = 0;
end
end
if dig(1) == 0
dig = dig(2:end);
end
end
</syntaxhighlight>
{{out}}
<pre>
0 : 0
1 : 1
2 : 10
3 : 100
4 : 101
5 : 1000
6 : 1001
7 : 1010
8 : 10000
9 : 10001
10 : 10010
11 : 10100
12 : 10101
13 : 100000
14 : 100001
15 : 100010
16 : 100100
17 : 100101
18 : 101000
19 : 101001
20 : 101010
 
</pre>
 
=={{header|MiniScript}}==
<syntaxhighlight lang="miniscript">
fibonacci = function(val)
if val < 1 then return []
fib = []
a = 1; b = 2
while a <= val
fib.insert(0, a)
next = a + b
a = b
b = next
end while
return fib
end function
 
zeckendorf = function(val)
seq = fibonacci(val)
s = ""
for i in seq
onOff = val >= i and (s == "" or s[-1] == "0")
s += str(onOff)
val -= (i*onOff)
end for
return s
end function
 
for i in range(1, 20)
print [i, zeckendorf(i)]
end for
</syntaxhighlight>
{{out}}
<pre>[1, "1"]
[2, "10"]
[3, "100"]
[4, "101"]
[5, "1000"]
[6, "1001"]
[7, "1010"]
[8, "10000"]
[9, "10001"]
[10, "10010"]
[11, "10100"]
[12, "10101"]
[13, "100000"]
[14, "100001"]
[15, "100010"]
[16, "100100"]
[17, "100101"]
[18, "101000"]
[19, "101001"]
[20, "101010"]
</pre>
 
=={{header|Nim}}==
Line 4,062 ⟶ 4,545:
 
21 times
[ i^ dup echo
say " -> "
n->z dup binecho
say " -> "
z->n echo cr ]</syntaxhighlight>
 
{{Out}}
Line 4,487 ⟶ 4,970:
19: 101001
20: 101010</pre>
 
=={{header|Rust}}==
{{trans|C#}}
<syntaxhighlight lang="Rust">
use std::collections::VecDeque;
 
fn fibonacci(n: u32) -> u32 {
match n {
0 => 0,
1 => 1,
_ => fibonacci(n - 1) + fibonacci(n - 2),
}
}
 
fn zeckendorf(num: u32) -> String {
let mut fibonacci_numbers = VecDeque::new();
let mut fib_position = 2;
let mut current_fibonacci_num = fibonacci(fib_position);
 
while current_fibonacci_num <= num {
fibonacci_numbers.push_front(current_fibonacci_num);
fib_position += 1;
current_fibonacci_num = fibonacci(fib_position);
}
 
let mut temp = num;
let mut output = String::new();
 
for item in fibonacci_numbers {
if item <= temp {
output.push('1');
temp -= item;
} else {
output.push('0');
}
}
 
output
}
 
fn main() {
for i in 1..=20 {
let zeckendorf_representation = zeckendorf(i);
println!("{} : {}", i, zeckendorf_representation);
}
}
</syntaxhighlight>
{{out}}
<pre>
1 : 1
2 : 10
3 : 100
4 : 101
5 : 1000
6 : 1001
7 : 1010
8 : 10000
9 : 10001
10 : 10010
11 : 10100
12 : 10101
13 : 100000
14 : 100001
15 : 100010
16 : 100100
17 : 100101
18 : 101000
19 : 101001
20 : 101010
 
</pre>
 
=={{header|Scala}}==
Line 4,830 ⟶ 5,384:
19: 101001
20: 101010</pre>
 
=={{header|UNIX Shell}}==
<syntaxhighlight lang="sh">set -- 2 1
x=-1
while [ $((x += 1)) -le 20 ]
do
[ $x -gt $1 ] && set -- $(($2 + $1)) "$@"
n=$x zeck=''
for fib
do
zeck=$zeck$((n >= fib && (n -= fib) + 1))
done
echo "$x: ${zeck#0}"
done</syntaxhighlight>
{{out}}
<pre>0: 0
1: 1
2: 10
3: 100
4: 101
5: 1000
6: 1001
7: 1010
8: 10000
9: 10001
10: 10010
11: 10100
12: 10101
13: 100000
14: 100001
15: 100010
16: 100100
17: 100101
18: 101000
19: 101001
20: 101010</pre>
 
=={{header|V (Vlang)}}==
Line 4,892 ⟶ 5,482:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
 
var LIMIT = 46 // to stay within range of signed 32 bit integer
PureFox
9,482

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/337338...351725"