javascript - Masalah algoritma rekursif.

Question

Jika bos anda memberi anda satu yuan pada hari pertama, dia akan memberi anda dua kali ganda jumlah hari sebelumnya setiap hari. Iaitu 1, 2, 4, 8.... . Sekarang, selepas 30 hari, berapakah jumlah wang yang anda terima?
Keperluan: Gunakan fungsi rekursif untuk melaksanakan

Answer 1

Masalahnya sangat mudah, kuncinya terletak pada idea, berikut adalah kodnya.

/*
·递归
  1. salarySum(n) = salarySum(n-1) + salary(n)
  2. salary(n) = 2 ^ (n-1)

·非递归
  循环
*/

function salary(nthDay){
  return Math.pow(2, nthDay-1)
}

// 递归
function salarySum(nthDay) {
  if (nthDay > 1) {
    return salarySum(nthDay - 1) + salary(nthDay)
  } else {
    return 1
  }
}

// 非递归
function salarySum(nthDay) {
  let day = 1
  let sum = 0
  while (day <= nthDay) {
    sum += salary(day)
    day++
  }
  return sum
}

Answer 2

PHP版本

function recursion($day){
    if($day == 1){
        return 1;
    }else{
        return recursion($day - 1) + pow(2,$day - 1);
    }
}
echo recursion(30);

Answer 3

Haha malunya tersalah baca soalan

#不递归的实现方式
def fn(n):
    return 2 ** (n - 1)

#递归的实现方式
def fn1(n):
    return 1 if n <= 1 else fn1(n-1) * 2

Answer 4

#!/usr/bin/env python

def salary(n):
    '''Your salary everyday'''
    if n <= 1:
        return 1
    return 2*salary(n-1)


def money(n):
    '''Total money you get for n days.'''
    if n <= 0:
        return 0
    s = salary(n)  # or s = 2**(n-1)
    m = money(n-1)
    print("day %d: salary[%d] total[%d]" % (n, s, (s+m)))
    return s+m 

money(30)

hari 1: gaji[1] jumlah[1]
hari 2: gaji[2] jumlah[3]
hari 3: gaji[4] jumlah[7]
hari 4: gaji[8] jumlah[15]
hari 5: gaji[16] jumlah[31]
hari ke-6: gaji[32] jumlah[63]
hari ke-7: gaji[64] jumlah[127]
hari ke-8: gaji[128] jumlah[255]
hari ke-9: gaji[256] jumlah[511]
hari 10: gaji[512] jumlah[1023]
hari 11: gaji[1024] jumlah[2047]
hari 12: gaji[2048] jumlah[4095]
hari 13: gaji[ 4096] jumlah[8191]
hari ke-14: gaji[8192] jumlah[16383]
hari ke-15: gaji[16384] jumlah[32767]
hari ke-16: gaji[32768] jumlah[65535]
hari][17:35]
65:35 jumlah[131071]
hari ke-18: gaji[131072] jumlah[262143]
hari ke-19: gaji[262144] jumlah[524287]
hari ke-20: gaji[524288] jumlah[1048575]
4:8 hari 1048575 2097151]
hari ke-22: gaji[2097152] jumlah[4194303]
hari ke-23: gaji[4194304] jumlah[8388607]
hari ke-24: gaji[8388608] jumlah[1677:608] jumlah[1677:672] 33554431]
hari ke-26: gaji[33554432] jumlah[67108863]
hari ke-27: gaji[67108864] jumlah[134217727]
hari ke-28: gaji[134217728] jumlah[26843]954.25 hari [536870911]
hari 30: gaji[536870912] jumlah[1073741823]

Answer 5

Idea saya ialah: mula-mula mengira jumlah semasa, dan kemudian lulus tarikh dan jumlah hari ini sehingga pengiraan mencapai 30 hari.

function total(all, day,money){
    var day = day || 1,
        money = money || 0.5;

    money *= 2;
    // console.log( 'day'+day+': '+ money ); // 输出当前的金额
    day++;
    if(day<=all){
        return money + total(all, day, money);
    }
    return money;
}

Kemudian hubungi total():

total(1); // 1
total(2); // 3
total(7); // 127
total(30); // 1073741823