Programming Challenges #41

Recall the definition of the Fibonacci numbers:

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b].

Input

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a ≤ b ≤ 10100. The numbers a and b are given with no superfluous leading zeros.

Output

For each test case output on a single line the number of Fibonacci numbers fi with a ≤ fi ≤ b.

Sample Input

10 100

1234567890 9876543210

0 0

Sample Output

5

4

---

let a = new Array();
let b = new Array();
let fib = [new Array(), new Array(), new Array()];
let lengtha, lengthb;
let length = new Array();
let result = 0;

function compare(fi, len, arg) {
    if (length[fi] < len) {
        return -1;
    } else if (length[fi] > len) {
        return 1;
    }
    for (let i = len - 1; i >= 0; i--) {
        if (fib[fi][i] < arg[i]) {
            return -1;
        } else if (fib[fi][i] > arg[i]) {
            return 1;
        }
    }
    return 0;
}

function plus(target, a, b) {
    let carry = 0;
    let len = 0;
    for (len = 0; len < length[a] && len < length[b]; len++) {
        fib[target][len] = (fib[a][len] + fib[b][len] + carry);
        if (fib[target][len] >= 10) {
            carry = 1;
        } else {
            carry = 0;
        }
        fib[target][len] %= 10;
    }
    if (len < length[a]) {
        for (; len < length[a]; len++) {
            fib[target][len] = (fib[a][len] + carry);
            if (fib[target][len] >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }
            fib[target][len] %= 10;
        }
    } else {
        for (; len < length[b]; len++) {
            fib[target][len] = (fib[b][len] + carry);
            if (fib[target][len] >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }
            fib[target][len] %= 10;
        }
    }

    if (carry) {
        fib[target][len++] = 1;
    }
    length[target] = len;
}

function main() {
    let i = 0;
    length[0] = length[1] = 1;
    fib[0][0] = fib[1][0] = 1; 
    for (i = 0; compare(i % 3, lengtha, a) < 0; i++) {
        plus((i + 1) % 3, i % 3, (i - 1) % 3);
    }
    result = i;
    for (; compare(i % 3, lengthb, b) <= 0; i++) {
        plus((i + 1) % 3, i % 3, (i - 1) % 3);
    }
    result = i - result;
    console.log(`result : ${result}`);
}

// const x = '10';
// const y = '100';

const x = '1234567890';
const y = '9876543210';

let tempa = x.split('');
let tempb = y.split('');

lengtha = tempa.length;
lengthb = tempb.length;

console.log(lengtha)
console.log(lengthb)

tempa.forEach((v, i, arr) => {
    a[i] = tempa[lengtha - i - 1] - '0';
})
tempb.forEach((v, i, arr) => {
    b[i] = tempb[lengthb - i - 1] - '0';
})

console.log(a)
console.log(b)

main()

1. 배열 a와 b를 생성하고, 각각 tempa와 tempb의 값을 역순으로 저장합니다.
2. lengtha와 lengthb 변수를 생성하고, 각각 tempa와 tempb의 길이를 저장합니다.
3. length 배열과 fib 배열은 각각 피보나치 수열의 길이와 값들을 저장하기 위한 배열입니다.
   • length[0] = length[1] = 1;은 length 배열의 첫 번째와 두 번째 요소를 1로 초기화하는 것입니다. 이는 피보나치 수열의 첫 번째와 두 번째 값의 길이가 1이라는 의미입니다. fib[0][0] = fib[1][0] = 1;은 fib 배열의 첫 번째와 두 번째 배열의 첫 번째 요소를 1로 초기화하는 것입니다. 이는 피보나치 수열의 첫 번째와 두 번째 값이 각각 1이라는 의미입니다. 이렇게 초기화를 진행하면 피보나치 수열 계산에 사용되는 초기 조건을 설정할 수 있습니다. 초기 값으로 1을 설정하는 이유는 피보나치 수열에서 첫 번째와 두 번째 값이 1로 시작하기 때문입니다. 이렇게 초기화된 length 배열과 fib 배열을 바탕으로 피보나치 수열을 계산하고 결과를 저장하게 됩니다.

1. main() 함수를 호출하여 피보나치 수열을 계산합니다.
2. main() 함수 내에서 compare() 함수를 사용하여 lengtha와 a 배열을 비교하여 반복문을 실행합니다.
   • compare() 함수는 두 개의 피보나치 수열을 비교하기 위해 사용됩니다. 피보나치 수열은 이전의 두 값의 합으로 이루어져 있기 때문에, 계산된 수열의 크기를 비교하기 위해서는 비교 연산이 필요합니다. compare() 함수는 세 개의 매개변수를 받습니다. fi는 비교 대상인 피보나치 수열의 인덱스를 나타내고, len은 비교 대상인 피보나치 수열의 길이를 나타냅니다. arg는 비교할 피보나치 수열을 나타내는 배열입니다.
   • compare() 함수는 다음과 같은 로직으로 수행됩니다
     • length[fi]와 len을 비교하여 길이가 작을 경우 -1을 반환합니다
     • length[fi]와 len이 같은 경우, 피보나치 수열의 값들을 인덱스별로 비교합니다
     • 값들을 역순으로 비교하면서, 만약 fib[fi][i]가 arg[i]보다 작으면 -1을 반환합니다
     • 만약 fib[fi][i]가 arg[i]보다 크면 1을 반환합니다
     • 모든 값들이 같다면 0을 반환합니다.
   • 따라서 compare() 함수를 사용하여 두 개의 피보나치 수열을 비교할 수 있습니다. 이를 통해 특정 조건에 따라 피보나치 수열을 계산하고, 수열의 크기나 값들을 비교하여 원하는 조건에 따라 작업을 수행할 수 있습니다.

1. 반복문을 통해 plus() 함수를 호출하여 피보나치 수열을 계산하고, result 변수에 결과값을 저장합니다.
   1. plus() 함수는 두 개의 피보나치 수열을 더하고, 결과를 새로운 피보나치 수열로 저장하기 위해 사용됩니다. 코드에서 plus() 함수는 다음과 같은 목적으로 사용됩니다.
      1. plus() 함수는 두 개의 피보나치 수열을 더하여 새로운 피보나치 수열을 생성합니다. 피보나치 수열의 특성상, 현재 인덱스의 값은 이전 두 인덱스의 값의 합으로 계산됩니다. plus() 함수는 이러한 덧셈 연산을 수행하여 새로운 피보나치 수열을 생성합니다
      2. 피보나치 수열의 각 자릿수 값은 0부터 9까지의 정수로 제한되어 있습니다. plus() 함수는 덧셈 연산 결과에서 10을 초과하는 값에 대해 자릿수 올림(carry)을 처리합니다. 각 자릿수에 대해 10을 초과하는 값이 나오면 해당 자릿수의 값은 10으로 나눈 나머지가 되고, 다음 자릿수에는 10을 나눈 몫이 자릿수 올림으로 처리됩니다.
      3. plus() 함수는 새로운 피보나치 수열의 길이를 업데이트합니다. 피보나치 수열은 이전 두 수열의 합으로 구성되기 때문에, 새로운 수열의 길이는 이전 두 수열의 길이 중 더 긴 값을 가집니다. plus() 함수는 두 수열의 길이를 비교하여 더 긴 값을 선택하고, 새로운 수열의 길이를 업데이트합니다.
   2.  plus() 함수는 피보나치 수열의 덧셈 연산과 자릿수 올림 처리, 그리고 새로운 수열의 길이 업데이트를 수행하여 피보나치 수열을 계산하는 데 사용됩니다. 위 코드에서 plus() 함수는 main() 함수에서 피보나치 수열의 계산에 활용되고 있습니다.

1. 두 번째 반복문에서는 lengthb와 b 배열을 비교하여 피보나치 수열을 계산하고, result 값을 갱신합니다.
2. 최종적으로 result 값을 출력합니다.