////////// Exercice 1 ////////// // Sums `a` and `b` using only +1 and -1 operations function plusTailRec(a, b) { if (b === 0) return a; else return plusTailRec(a+1, b-1); } function testPlus(a, b, expected) { const res = expected === plusTailRec(a, b) ? 'OK' : 'KO'; console.log(`Test plusTailRec(${a}, ${b}) : ${res}`); } testPlus(7, 12, 19); testPlus(7, 0, 7); testPlus(0, 12, 12); // Multiplies `a` and `b` using only +a operations function productTailRec(a, b) { function productInternal(a, b, acc) { if (b === 0) return acc; else return productInternal(a, b-1, acc+a); } return productInternal(a, b, 0); } function testProd(a, b, expected) { const res = expected === productTailRec(a, b) ? 'OK' : 'KO'; console.log(`Test productTailRec(${a}, ${b}) : ${res}`); } testProd(3, 5, 15); testProd(3, 0, 0); testProd(3, 1, 3); testProd(1, 5, 5); ////////// Exercice 2 ////////// // Computes x^n // Precond : `n` is a non-negative integer function powerLinearTr(x, n) { // powerLinearAux(x, n, acc) = x^n * acc function powerLinearAux(x, n, acc) { if (n > 0) return powerLinearAux(x, n-1, x*acc); else return acc; } return powerLinearAux(x, n, 1); } console.log(`powerLinearTr(2, 10) = ${powerLinearTr(2, 10)}`); // -> 1024 console.log(`powerLinearTr(5, 3) = ${powerLinearTr(5, 3)}`); // -> 125 console.log(`powerLinearTr(2, 5) = ${powerLinearTr(2, 5)}`); // -> 32 // Computes x^n using greedy algorithm / logarithmic approach // Precond : `n` is a non-negative integer function powerLogTr(x, n) { // powerLogAux(x, n, acc) = x^n * acc function powerLogAux(x, n, acc) { if ( n === 0 ) { // x^0 * acc = acc return acc; } else if (n%2 === 0) { // n = 2m // x^(2m) * acc = (x^2)^m * acc return powerLogAux(x*x, n/2, acc); } else { // n = 2m + 1 // x^(2m+1) * acc = x^(2m) * (x * acc) return powerLogAux(x, n-1, acc*x); } } return powerLogAux(x, n, 1); } console.log(`powerLogTr(2, 10) = ${powerLogTr(2, 10)}`); // -> 1024 console.log(`powerLogTr(5, 3) = ${powerLogTr(5, 3)}`); // -> 125 console.log(`powerLogTr(2, 5) = ${powerLogTr(2, 5)}`); // -> 32 ////////// Exercice 3 ////////// // Computes the `n`th element of the Fibonacci sequence function fibo(n) { if (n <= 2) return 1; else return fibo(n-1) + fibo(n-2); } [1,2,3,4,5,6].forEach((el) => { console.log(`fibo(${el}) = ${fibo(el)}`); }); // Computes the `n`th element of the generalized Fibonacci // sequence function fiboGen(n, a, b) { if (n === 1) return a; else if (n === 2) return b; else return fiboGen(n-1, a, b) + fiboGen(n-2, a, b); } [1,2,3,4,5,6].forEach((el) => { console.log(`fiboGen(${el}, 1, 1) = ${fiboGen(el, 1, 1)}`); }); // Computes the `n`th element of the generalized Fibonacci // sequence in a tail-recursive manner function fiboTailRec(n, a, b) { if (n === 1) return a; else return fiboTailRec(n-1, b, a+b); } [1,2,3,4,5,6].forEach((el) => { console.log(`fiboTailRec(${el}, 1, 1) = ${fiboTailRec(el, 1, 1)}`); }); // Computes the `n`th element of the generalized Fibonacci sequence // in a tail-recursive manner, with memoization // (this is not in the scope of the exercise, simply a demo of how to // combine tail-recursion and memoization) function makeFiboMemo() { const memo = {}; function fiboTailRec(n, a, b) { if (n === 1) return a; else return fiboTailRec(n-1, b, a+b); } function fibo(n) { if (memo[n]) return memo[n]; else { memo[n] = fiboTailRec(n, 1, 1); return memo[n]; } } return fibo; } const myFibo = makeFiboMemo(); [1,2,3,4,5,6].forEach((el) => { console.log(`fiboMemo(${el}) = ${myFibo(el)}`); }); ////////// Exercice 4 ////////// function frozenFact(n, p) { if (n <= 1n) return p; // Could also be () => p but less efficient else return () => frozenFact(n-1n, n*p); } console.log(`typeof frozenFact(4, 1) = ${typeof frozenFact(4, 1)}`); // -> function console.log(`typeof frozenFact(4, 1)() = ${typeof frozenFact(4n, 1n)()}`); // -> function console.log(`typeof frozenFact(4n, 1n)()() = ${typeof frozenFact(4n, 1n)()()}`); // -> function console.log(`typeof frozenFact(4n, 1n)()()() = ${typeof frozenFact(4n, 1n)()()()}`); // -> bigint function trampoline(v) { while (v instanceof Function) { v = v(); } return v; } console.log(`trampoline(frozenFact(10n, 1n)) = ${trampoline(frozenFact(10n, 1n))}`); // -> 3628800 function factTot(n) { function frozenFact(n, p) { if (n <= 1n) return p; // Could also be () => p but less efficient else return () => frozenFact(n-1n, n*p); } return trampoline(frozenFact(n, 1n)); } function fiboTot(n) { function frozenFibo(n, a, b) { if (n <= 1n) return a; // Could also be () => a but less efficient else return () => frozenFibo(n-1n, b, a+b); } return trampoline(frozenFibo(n, 1n, 1n)); } ////////// Exercice 5 ////////// //////////////////////////////////////////////////////////////// function getP(prices, i) { // Return the price if any, otherwise 0 return (i < prices.length) ? prices[i] : 0; } //////////////////////////////////////////////////////////////// // Return the max of f over [a..b[, where f returns numerical values // If [a..b[ is empty, returns undefined function maxGen(f, a, b) { function maxGenRec(a, b, acc) { if (a > b) return acc; else return maxGenRec(a+1, b, Math.max(f(a), acc)); } if (a > b) return undefined; else return maxGenRec(a+1, b, f(a)); } console.log(`Max of square fun over [-5;5] : ${maxGen((i) => i*i, -5, 5)}`); console.log(`Max of square fun over [5;-5] : ${maxGen((i) => i*i, 5, -5)}`); //////////////////////////////////////////////////////////////// function cuttingStock(prices, L) { if (L <= 0) return 0; else { function f(i) { return getP(prices, i) + cuttingStock(prices,L-i); } return maxGen(f,1,L); } } const prices1 = [0, 1, 5, 8, 9, 10, 17]; const prices2 = [0, 3, 5, 8, 9, 10, 17]; function testCuttingStock(prices, L) { console.log(`Max profit with prices [${prices}] L=${L} : ${cuttingStock(prices, L)}`); } for (let i=1; i<6; i++) testCuttingStock(prices1, i); testCuttingStock(prices1, 8); testCuttingStock(prices2, 8); //////////////////////////////////////////////////////////////// const memo = { 0: 0 }; // i.e the cost for length 0 is 0 function cuttingStockMemo(prices, L) { if (memo[L] || L === 0) // *must* add test for 0, because memo[0] === false return memo[L]; else { function f(i) { return getP(prices, i) + cuttingStockMemo(prices, L-i); } memo[L] = maxGen(f,1,L); return memo[L]; } } function testCuttingStockMemo(prices, L) { console.log(`Max profit with prices [${prices}] L=${L} : ${cuttingStockMemo(prices, L)}`); } const prices3 = [0, 2, 5, 7, 9, 11, 17]; for (let i=1; i<3; i++) testCuttingStockMemo(prices3, i); testCuttingStockMemo(prices3, 8); testCuttingStockMemo(prices3, 9); console.log(memo); //////////////////////////////////////////////////////////////// function cuttingStockMemoInternal(prices) { const memo = { 0: 0 }; function cSM(L) { if (memo[L] || L === 0) return memo[L]; else { function f(i) { return getP(prices, i) + cuttingStockMemo(prices, L-i); } memo[L] = maxGen(f,1,L); return memo[L]; } } return cSM; } let myCuttingStock = cuttingStockMemoInternal(prices3); function testCuttingStockMemoInt(prices, L) { console.log(`Max profit with prices [${prices}] L=${L} is ${myCuttingStock(L)}`); } for (let i=1; i<6; i++) testCuttingStockMemoInt(prices3, i); testCuttingStockMemoInt(prices3, 8); testCuttingStockMemoInt(prices3, 9);