Algorithms - JavaScript - 基礎概念 - 数学的な基礎(帰納法、Fibonacci 数と黄金比、大小、等式)

The Art of Computer Programming
Volume 1
原著

開発環境

macOS Sierra - Apple (OS)
Emacs (Text Editor)
JavaScript (プログラミング言語)
Node.js, Safari(JavaScript エンジン)
Learning JavaScript [邦訳](参考書籍)

The Art of Computer Programming　Volume 1 Fundamental Algorithms Third Edition 日本語版(Donald E. Knuth (著)、青木孝 (著)、筧一彦 (著)、鈴木健一 (著)、長尾高弘 (著)、有澤誠 (その他)、和田英一 (その他)、ドワンゴ)の第1章(基礎概念)、1.2(数学的な基礎)、演習問題4を取り組んでみる。

$\begin{array}{l} ϕ = \frac{\sqrt{5} + 1}{2} \\ F_{1} = 1 \geq \frac{2}{\sqrt{5} + 1} = ϕ^{- 1} = ϕ^{1 - 2} \\ F_{2} = 1 \geq 1 = ϕ^{0} = ϕ^{2 - 2} \\ F_{n + 1} = F_{n - 1} + F_{n} \\ \geq ϕ^{n - 3} + ϕ^{n - 2} \\ = ϕ^{n - 3} (1 + ϕ) \\ = ϕ^{n - 3} \cdot ϕ^{2} \\ = ϕ^{n - 1} \\ = ϕ^{(n + 1) - 2} \end{array}$

コード(Emacs)

HTML5

n = <input id="n0" type="number" min="0" step="1" value="100">
<br>
<button id="run0">run</button>
<button id="clear0">clear</button>
<pre id="output0"></pre>

<script src="sample4.js"></script>

JavaScript

let input0 = document.querySelector('#n0'),
    btn0 = document.querySelector('#run0'),
    btn1 = document.querySelector('#clear0'),
    pre0 = document.querySelector('#output0'),
    p = (x) => pre0.textContent += x + '\n';

let goldenRatio = (1 + Math.sqrt(5)) / 2;

let fibnacci = (n) => {
    let a = 0;
    let b = 1;
    for (i = 2; i <= n; i += 1) {
        b = a + b;
        a = b - a;
    }
    return b;
};

let output = () => {
    let n = parseInt(input0.value, 10);

    p(`n, φ^{n-2}, fibonacci(n), φ^{n-1}, φ^{n-2} <= fibonacci(n) <= φ^{n-1}`);
    for (let i = 0; i <= n; i += 1) {
        let x = Math.pow(goldenRatio, i - 2),
            y = fibnacci(i),
            z = Math.pow(goldenRatio, i - 1);
        p(`${i}, ${x}, ${y}, ${z}: ${x <= y && y <= z}`);
    }
};
    

btn0.onclick = output;
btn1.onclick = () => {
    pre0.textContent = '';
};

output();

n =

n, φ^{n-2}, fibonacci(n), φ^{n-1}, φ^{n-2} <= fibonacci(n) <= φ^{n-1}
0, 0.3819660112501051, 1, 0.6180339887498948: false
1, 0.6180339887498948, 1, 1: true
2, 1, 1, 1.618033988749895: true
3, 1.618033988749895, 2, 2.618033988749895: true
4, 2.618033988749895, 3, 4.23606797749979: true
5, 4.23606797749979, 5, 6.854101966249686: true
6, 6.854101966249686, 8, 11.090169943749476: true
7, 11.090169943749476, 13, 17.944271909999163: true
8, 17.944271909999163, 21, 29.03444185374864: true
9, 29.03444185374864, 34, 46.978713763747805: true
10, 46.978713763747805, 55, 76.01315561749645: true
11, 76.01315561749645, 89, 122.99186938124426: true
12, 122.99186938124426, 144, 199.0050249987407: true
13, 199.0050249987407, 233, 321.996894379985: true
14, 321.996894379985, 377, 521.0019193787257: true
15, 521.0019193787257, 610, 842.9988137587108: true
16, 842.9988137587108, 987, 1364.0007331374366: true
17, 1364.0007331374366, 1597, 2206.9995468961474: true
18, 2206.9995468961474, 2584, 3571.000280033584: true
19, 3571.000280033584, 4181, 5777.999826929732: true
20, 5777.999826929732, 6765, 9349.000106963316: true
21, 9349.000106963316, 10946, 15126.999933893048: true
22, 15126.999933893048, 17711, 24476.000040856365: true
23, 24476.000040856365, 28657, 39602.999974749415: true
24, 39602.999974749415, 46368, 64079.00001560579: true
25, 64079.00001560579, 75025, 103681.99999035521: true
26, 103681.99999035521, 121393, 167761.000005961: true
27, 167761.000005961, 196418, 271442.9999963162: true
28, 271442.9999963162, 317811, 439204.00000227726: true
29, 439204.00000227726, 514229, 710646.9999985935: true
30, 710646.9999985935, 832040, 1149851.0000008708: true
31, 1149851.0000008708, 1346269, 1860497.9999994645: true
32, 1860497.9999994645, 2178309, 3010349.0000003353: true
33, 3010349.0000003353, 3524578, 4870846.9999998: true
34, 4870846.9999998, 5702887, 7881196.000000136: true
35, 7881196.000000136, 9227465, 12752042.999999937: true
36, 12752042.999999937, 14930352, 20633239.000000075: true
37, 20633239.000000075, 24157817, 33385282.00000001: true
38, 33385282.00000001, 39088169, 54018521.00000009: true
39, 54018521.00000009, 63245986, 87403803.00000009: true
40, 87403803.00000009, 102334155, 141422324.00000018: true
41, 141422324.00000018, 165580141, 228826127.0000003: true
42, 228826127.0000003, 267914296, 370248451.0000005: true
43, 370248451.0000005, 433494437, 599074578.0000008: true
44, 599074578.0000008, 701408733, 969323029.0000014: true
45, 969323029.0000014, 1134903170, 1568397607.0000024: true
46, 1568397607.0000024, 1836311903, 2537720636.000004: true
47, 2537720636.000004, 2971215073, 4106118243.000006: true
48, 4106118243.000006, 4807526976, 6643838879.0000105: true
49, 6643838879.0000105, 7778742049, 10749957122.000017: true
50, 10749957122.000017, 12586269025, 17393796001.00003: true
51, 17393796001.00003, 20365011074, 28143753123.000046: true
52, 28143753123.000046, 32951280099, 45537549124.00008: true
53, 45537549124.00008, 53316291173, 73681302247.00012: true
54, 73681302247.00012, 86267571272, 119218851371.00021: true
55, 119218851371.00021, 139583862445, 192900153618.00037: true
56, 192900153618.00037, 225851433717, 312119004989.0006: true
57, 312119004989.0006, 365435296162, 505019158607.001: true
58, 505019158607.001, 591286729879, 817138163596.0016: true
59, 817138163596.0016, 956722026041, 1322157322203.0024: true
60, 1322157322203.0024, 1548008755920, 2139295485799.0042: true
61, 2139295485799.0042, 2504730781961, 3461452808002.007: true
62, 3461452808002.007, 4052739537881, 5600748293801.012: true
63, 5600748293801.012, 6557470319842, 9062201101803.02: true
64, 9062201101803.02, 10610209857723, 14662949395604.031: true
65, 14662949395604.031, 17167680177565, 23725150497407.05: true
66, 23725150497407.05, 27777890035288, 38388099893011.086: true
67, 38388099893011.086, 44945570212853, 62113250390418.14: true
68, 62113250390418.14, 72723460248141, 100501350283429.22: true
69, 100501350283429.22, 117669030460994, 162614600673847.38: true
70, 162614600673847.38, 190392490709135, 263115950957276.62: true
71, 263115950957276.62, 308061521170129, 425730551631124: true
72, 425730551631124, 498454011879264, 688846502588400.6: true
73, 688846502588400.6, 806515533049393, 1114577054219524.8: true
74, 1114577054219524.8, 1304969544928657, 1803423556807925.5: true
75, 1803423556807925.5, 2111485077978050, 2918000611027450: true
76, 2918000611027450, 3416454622906707, 4721424167835376: true
77, 4721424167835376, 5527939700884757, 7639424778862826: true
78, 7639424778862826, 8944394323791464, 12360848946698204: true
79, 12360848946698204, 14472334024676220, 20000273725561030: true
80, 20000273725561030, 23416728348467684, 32361122672259236: true
81, 32361122672259236, 37889062373143900, 52361396397820270: true
82, 52361396397820270, 61305790721611580, 84722519070079500: true
83, 84722519070079500, 99194853094755490, 137083915467899780: true
84, 137083915467899780, 160500643816367070, 221806434537979300: true
85, 221806434537979300, 259695496911122560, 358890350005879100: true
86, 358890350005879100, 420196140727489660, 580696784543858400: true
87, 580696784543858400, 679891637638612200, 939587134549737600: true
88, 939587134549737600, 1100087778366101900, 1520283919093596200: true
89, 1520283919093596200, 1779979416004714000, 2459871053643333600: true
90, 2459871053643333600, 2880067194370816000, 3980154972736930000: true
91, 3980154972736930000, 4660046610375530000, 6440026026380263000: true
92, 6440026026380263000, 7540113804746346000, 10420180999117193000: true
93, 10420180999117193000, 12200160415121877000, 16860207025497459000: true
94, 16860207025497459000, 19740274219868226000, 27280388024614654000: true
95, 27280388024614654000, 31940434634990105000, 44140595050112115000: true
96, 44140595050112115000, 51680708854858334000, 71420983074726770000: true
97, 71420983074726770000, 83621143489848440000, 115561578124838900000: true
98, 115561578124838900000, 135301852344706780000, 186982561199565670000: true
99, 186982561199565670000, 218922995834555200000, 302544139324404600000: true
100, 302544139324404600000, 354224848179262000000, 489526700523970300000: true

Kamimura's blog

ほしい物リスト

2017年4月13日木曜日

Algorithms - JavaScript - 基礎概念 - 数学的な基礎(帰納法、Fibonacci 数と黄金比、大小、等式)

0 コメント:

コメントを投稿