Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
12 changes: 6 additions & 6 deletions 1-js/06-advanced-functions/01-recursion/01-sum-to/solution.md
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
The solution using a loop:
วิธีใช้ลูป:

```js run
function sumTo(n) {
Expand All @@ -12,7 +12,7 @@ function sumTo(n) {
alert( sumTo(100) );
```

The solution using recursion:
วิธีใช้การเรียกซ้ำ:

```js run
function sumTo(n) {
Expand All @@ -23,7 +23,7 @@ function sumTo(n) {
alert( sumTo(100) );
```

The solution using the formula: `sumTo(n) = n*(n+1)/2`:
วิธีใช้สูตร: `sumTo(n) = n*(n+1)/2`:

```js run
function sumTo(n) {
Expand All @@ -33,8 +33,8 @@ function sumTo(n) {
alert( sumTo(100) );
```

P.S. Naturally, the formula is the fastest solution. It uses only 3 operations for any number `n`. The math helps!
P.S. แน่นอนว่าสูตรคณิตศาสตร์เร็วที่สุด ใช้แค่ 3 การดำเนินการไม่ว่า `n` จะเป็นเท่าไหร่ คณิตศาสตร์ช่วยได้!

The loop variant is the second in terms of speed. In both the recursive and the loop variant we sum the same numbers. But the recursion involves nested calls and execution stack management. That also takes resources, so it's slower.
วิธีลูปเร็วเป็นอันดับสอง ทั้งแบบเรียกซ้ำและแบบลูปบวกตัวเลขชุดเดียวกัน แต่การเรียกซ้ำมีการเรียกฟังก์ชันซ้อนและจัดการ execution stack ซึ่งกินทรัพยากรเพิ่ม จึงช้ากว่า

P.P.S. Some engines support the "tail call" optimization: if a recursive call is the very last one in the function, with no other calculations performed, then the outer function will not need to resume the execution, so the engine doesn't need to remember its execution context. That removes the burden on memory. But if the JavaScript engine does not support tail call optimization (most of them don't), there will be an error: maximum stack size exceeded, because there's usually a limitation on the total stack size.
P.P.S. บาง engine รองรับการปรับแต่ง "tail call" คือถ้าการเรียกซ้ำเป็นคำสั่งสุดท้ายของฟังก์ชัน โดยไม่มีการคำนวณอื่นอีก ฟังก์ชันภายนอกก็ไม่ต้องกลับมาทำงานต่อ ดังนั้น engine ไม่ต้องจำ execution context ช่วยลดภาระหน่วยความจำได้ แต่ถ้า JavaScript engine ไม่รองรับ tail call optimization (ส่วนใหญ่ไม่รองรับ) ก็จะเกิด error: maximum stack size exceeded เพราะปกติจะมีการจำกัดขนาดสแต็กรวมไว้
22 changes: 11 additions & 11 deletions 1-js/06-advanced-functions/01-recursion/01-sum-to/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,11 +2,11 @@ importance: 5

---

# Sum all numbers till the given one
# หาผลรวมของตัวเลขทั้งหมดจนถึงจำนวนที่กำหนด

Write a function `sumTo(n)` that calculates the sum of numbers `1 + 2 + ... + n`.
เขียนฟังก์ชัน `sumTo(n)` ที่คำนวณผลรวมของตัวเลข `1 + 2 + ... + n`

For instance:
ตัวอย่าง:

```js no-beautify
sumTo(1) = 1
Expand All @@ -17,20 +17,20 @@ sumTo(4) = 4 + 3 + 2 + 1 = 10
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050
```

Make 3 solution variants:
เขียนคำตอบ 3 แบบ:

1. Using a for loop.
2. Using a recursion, cause `sumTo(n) = n + sumTo(n-1)` for `n > 1`.
3. Using the [arithmetic progression](https://en.wikipedia.org/wiki/Arithmetic_progression) formula.
1. ใช้ for loop
2. ใช้การเรียกซ้ำ เพราะ `sumTo(n) = n + sumTo(n-1)` เมื่อ `n > 1`
3. ใช้สูตร[อนุกรมเลขคณิต](https://en.wikipedia.org/wiki/Arithmetic_progression)

An example of the result:
ตัวอย่างผลลัพธ์:

```js
function sumTo(n) { /*... your code ... */ }
function sumTo(n) { /*... โค้ดของคุณ ... */ }

alert( sumTo(100) ); // 5050
```

P.S. Which solution variant is the fastest? The slowest? Why?
P.S. วิธีไหนเร็วที่สุด? ช้าที่สุด? ทำไม?

P.P.S. Can we use recursion to count `sumTo(100000)`?
P.P.S. เราใช้การเรียกซ้ำคำนวณ `sumTo(100000)` ได้ไหม?
Original file line number Diff line number Diff line change
@@ -1,6 +1,6 @@
By definition, a factorial `n!` can be written as `n * (n-1)!`.
จากนิยาม แฟกทอเรียล `n!` เขียนได้เป็น `n * (n-1)!`

In other words, the result of `factorial(n)` can be calculated as `n` multiplied by the result of `factorial(n-1)`. And the call for `n-1` can recursively descend lower, and lower, till `1`.
พูดอีกอย่างก็คือ ผลลัพธ์ของ `factorial(n)` คือ `n` คูณกับผลลัพธ์ของ `factorial(n-1)` แล้วการเรียกที่ `n-1` ก็เรียกซ้ำลดลงไปเรื่อยๆ จนถึง `1`

```js run
function factorial(n) {
Expand All @@ -10,7 +10,7 @@ function factorial(n) {
alert( factorial(5) ); // 120
```

The basis of recursion is the value `1`. We can also make `0` the basis here, doesn't matter much, but gives one more recursive step:
ฐานของการเรียกซ้ำคือค่า `1` เราจะใช้ `0` เป็นฐานแทนก็ได้ ไม่ต่างกันมาก แค่เพิ่มขั้นตอนการเรียกซ้ำอีกหนึ่งครั้ง:

```js run
function factorial(n) {
Expand Down
12 changes: 6 additions & 6 deletions 1-js/06-advanced-functions/01-recursion/02-factorial/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,17 +2,17 @@ importance: 4

---

# Calculate factorial
# คำนวณแฟกทอเรียล

The [factorial](https://en.wikipedia.org/wiki/Factorial) of a natural number is a number multiplied by `"number minus one"`, then by `"number minus two"`, and so on till `1`. The factorial of `n` is denoted as `n!`
[แฟกทอเรียล](https://en.wikipedia.org/wiki/Factorial)ของจำนวนธรรมชาติ คือการนำจำนวนนั้นคูณกับ "จำนวนนั้นลบหนึ่ง" แล้วคูณกับ "จำนวนนั้นลบสอง" ไปเรื่อยๆ จนถึง `1` แฟกทอเรียลของ `n` เขียนแทนด้วย `n!`

We can write a definition of factorial like this:
เขียนเป็นนิยามได้แบบนี้:

```js
n! = n * (n - 1) * (n - 2) * ...*1
```

Values of factorials for different `n`:
ค่าแฟกทอเรียลของ `n` ค่าต่างๆ:

```js
1! = 1
Expand All @@ -22,10 +22,10 @@ Values of factorials for different `n`:
5! = 5 * 4 * 3 * 2 * 1 = 120
```

The task is to write a function `factorial(n)` that calculates `n!` using recursive calls.
โจทย์คือเขียนฟังก์ชัน `factorial(n)` ที่คำนวณ `n!` โดยใช้การเรียกซ้ำ

```js
alert( factorial(5) ); // 120
```

P.S. Hint: `n!` can be written as `n * (n-1)!` For instance: `3! = 3*2! = 3*2*1! = 6`
P.S. คำใบ้: `n!` เขียนในรูป `n * (n-1)!` ได้ เช่น `3! = 3*2! = 3*2*1! = 6`
Original file line number Diff line number Diff line change
@@ -1,6 +1,6 @@
The first solution we could try here is the recursive one.
วิธีแรกที่ลองได้คือแบบเรียกซ้ำ

Fibonacci numbers are recursive by definition:
ตัวเลขฟีโบนักชีถูกนิยามแบบเรียกซ้ำอยู่แล้ว:

```js run
function fib(n) {
Expand All @@ -9,14 +9,14 @@ function fib(n) {

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // will be extremely slow!
// fib(77); // จะช้ามาก!
```

...But for big values of `n` it's very slow. For instance, `fib(77)` may hang up the engine for some time eating all CPU resources.
...แต่ถ้า `n` มีค่ามาก จะช้ามากๆ เช่น `fib(77)` อาจทำให้ engine ค้างเลย เพราะกิน CPU ไปหมด

That's because the function makes too many subcalls. The same values are re-evaluated again and again.
ที่เป็นแบบนี้เพราะฟังก์ชันเรียกซ้อนมากเกินไป ค่าเดิมๆ ถูกคำนวณซ้ำแล้วซ้ำอีก

For instance, let's see a piece of calculations for `fib(5)`:
ลองดูส่วนหนึ่งของการคำนวณ `fib(5)`:

```js no-beautify
...
Expand All @@ -25,68 +25,68 @@ fib(4) = fib(3) + fib(2)
...
```

Here we can see that the value of `fib(3)` is needed for both `fib(5)` and `fib(4)`. So `fib(3)` will be called and evaluated two times completely independently.
จะเห็นว่าค่า `fib(3)` ถูกใช้ทั้งใน `fib(5)` และ `fib(4)` ดังนั้น `fib(3)` จะถูกเรียกและคำนวณซ้ำสองครั้งโดยอิสระต่อกัน

Here's the full recursion tree:
นี่คือต้นไม้การเรียกซ้ำทั้งหมด:

![fibonacci recursion tree](fibonacci-recursion-tree.svg)

We can clearly notice that `fib(3)` is evaluated two times and `fib(2)` is evaluated three times. The total amount of computations grows much faster than `n`, making it enormous even for `n=77`.
เห็นชัดเลยว่า `fib(3)` ถูกคำนวณสองครั้ง และ `fib(2)` ถูกคำนวณสามครั้ง จำนวนการคำนวณทั้งหมดเพิ่มขึ้นเร็วกว่า `n` มาก จนมหาศาลแม้แค่ `n=77`

We can optimize that by remembering already-evaluated values: if a value of say `fib(3)` is calculated once, then we can just reuse it in future computations.
เราแก้ปัญหาได้โดยจำค่าที่คำนวณไปแล้ว: ถ้า `fib(3)` คำนวณแล้วครั้งหนึ่ง ก็นำค่ากลับมาใช้ได้เลยในการคำนวณครั้งถัดไป

Another variant would be to give up recursion and use a totally different loop-based algorithm.
อีกทางเลือกหนึ่งคือเลิกใช้การเรียกซ้ำ แล้วใช้อัลกอริทึมแบบลูปแทนเลย

Instead of going from `n` down to lower values, we can make a loop that starts from `1` and `2`, then gets `fib(3)` as their sum, then `fib(4)` as the sum of two previous values, then `fib(5)` and goes up and up, till it gets to the needed value. On each step we only need to remember two previous values.
แทนที่จะเริ่มจาก `n` แล้วลดลง เราเริ่มจาก `1` กับ `2` แล้วหา `fib(3)` จากผลรวมของสองตัว จากนั้นหา `fib(4)` จากผลรวมของสองค่าก่อนหน้า แล้วก็ `fib(5)` ไล่ขึ้นไปเรื่อยๆ จนถึงค่าที่ต้องการ ในแต่ละรอบต้องจำแค่สองค่าก่อนหน้า

Here are the steps of the new algorithm in details.
รายละเอียดขั้นตอนของอัลกอริทึมใหม่:

The start:
จุดเริ่มต้น:

```js
// a = fib(1), b = fib(2), these values are by definition 1
// a = fib(1), b = fib(2) ค่าเหล่านี้เท่ากับ 1 ตามนิยาม
let a = 1, b = 1;

// get c = fib(3) as their sum
// หา c = fib(3) จากผลรวม
let c = a + b;

/* we now have fib(1), fib(2), fib(3)
/* ตอนนี้เรามี fib(1), fib(2), fib(3)
a b c
1, 1, 2
*/
```

Now we want to get `fib(4) = fib(2) + fib(3)`.
ต่อไปเราต้องการ `fib(4) = fib(2) + fib(3)`

Let's shift the variables: `a,b` will get `fib(2),fib(3)`, and `c` will get their sum:
เลื่อนตัวแปร: `a,b` จะรับค่า `fib(2),fib(3)` แล้ว `c` จะเป็นผลรวม:

```js no-beautify
a = b; // now a = fib(2)
b = c; // now b = fib(3)
a = b; // ตอนนี้ a = fib(2)
b = c; // ตอนนี้ b = fib(3)
c = a + b; // c = fib(4)

/* now we have the sequence:
/* ตอนนี้ลำดับเป็น:
a b c
1, 1, 2, 3
*/
```

The next step gives another sequence number:
ขั้นตอนถัดไปก็ได้ตัวเลขในลำดับอีกตัว:

```js no-beautify
a = b; // now a = fib(3)
b = c; // now b = fib(4)
a = b; // ตอนนี้ a = fib(3)
b = c; // ตอนนี้ b = fib(4)
c = a + b; // c = fib(5)

/* now the sequence is (one more number):
/* ตอนนี้ลำดับเป็น (เพิ่มอีกหนึ่งตัว):
a b c
1, 1, 2, 3, 5
*/
```

...And so on until we get the needed value. That's much faster than recursion and involves no duplicate computations.
...ทำไปเรื่อยๆ จนได้ค่าที่ต้องการ วิธีนี้เร็วกว่าการเรียกซ้ำมาก และไม่มีการคำนวณซ้ำ

The full code:
โค้ดเต็ม:

```js run
function fib(n) {
Expand All @@ -105,6 +105,6 @@ alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757
```

The loop starts with `i=3`, because the first and the second sequence values are hard-coded into variables `a=1`, `b=1`.
ลูปเริ่มที่ `i=3` เพราะค่าแรกและค่าที่สองของลำดับถูกกำหนดไว้แล้วในตัวแปร `a=1`, `b=1`

The approach is called [dynamic programming bottom-up](https://en.wikipedia.org/wiki/Dynamic_programming).
วิธีนี้เรียกว่า [dynamic programming แบบ bottom-up](https://en.wikipedia.org/wiki/Dynamic_programming)
Original file line number Diff line number Diff line change
Expand Up @@ -2,24 +2,24 @@ importance: 5

---

# Fibonacci numbers
# ตัวเลขฟีโบนักชี

The sequence of [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number) has the formula <code>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></code>. In other words, the next number is a sum of the two preceding ones.
ลำดับ[ตัวเลขฟีโบนักชี](https://en.wikipedia.org/wiki/Fibonacci_number)มีสูตรว่า <code>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></code> พูดง่ายๆ ก็คือ ตัวเลขถัดไปเป็นผลรวมของสองตัวก่อนหน้า

First two numbers are `1`, then `2(1+1)`, then `3(1+2)`, `5(2+3)` and so on: `1, 1, 2, 3, 5, 8, 13, 21...`.
สองตัวแรกคือ `1` จากนั้นก็เป็น `2(1+1)` แล้วก็ `3(1+2)`, `5(2+3)` ไปเรื่อยๆ: `1, 1, 2, 3, 5, 8, 13, 21...`

Fibonacci numbers are related to the [Golden ratio](https://en.wikipedia.org/wiki/Golden_ratio) and many natural phenomena around us.
ตัวเลขฟีโบนักชีมีความเกี่ยวข้องกับ[อัตราส่วนทอง](https://en.wikipedia.org/wiki/Golden_ratio)และปรากฏการณ์ทางธรรมชาติมากมายรอบตัวเรา

Write a function `fib(n)` that returns the `n-th` Fibonacci number.
เขียนฟังก์ชัน `fib(n)` ที่คืนค่าตัวเลขฟีโบนักชีลำดับที่ `n`

An example of work:
ตัวอย่างการทำงาน:

```js
function fib(n) { /* your code */ }
function fib(n) { /* โค้ดของคุณ */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757
```

P.S. The function should be fast. The call to `fib(77)` should take no more than a fraction of a second.
P.S. ฟังก์ชันต้องทำงานเร็ว การเรียก `fib(77)` ควรใช้เวลาไม่ถึงวินาที
Loading