Mathematical induction

精典例题 NOI 1.5 -45 金币

描述

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天）里，每天收到两枚金币；之后三天（第四、五、六天）里，每天收到三枚金币；之后四天（第七、八、九、十天）里，每天收到四枚金币……这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币（N为任意正整数）。

你需要编写一个程序，确定从第一天开始的给定天数内，骑士一共获得了多少金币。

输入

一个整数（范围1到10000），表示天数。

输出

骑士获得的金币数。

样例输入

6

样例输出

14

例题分析

第K-1次计算结题已经知道
   m天 |  m+1  ~  m+k  天             1, 2, 2, 3, 3, 3, 4, 4, 4, 4
  ----   ---------------             ---------------- ------------
  k-1个|      k个                          days(3)    +     4     = days(4)

days(1) = 1; 1                     发1个金币的天数结束时总金币数 days(1) =  k(k+1)/2 = 1*2/2 = 1
days(2) = days(1)+2 = 3; 2         发2个金币的天数结束时总金币数 days(2) =  k(k+1)/2 = 2*3/2 = 3
days(3) = days(2)+3 = 6; 3         发3个金币的天数结束时总金币数 days(3) =  k(k+1)/2 = 3*4/2 = 6 
days(4) = days(3)+4 = 10; 4        发4个的金币天数结束时总金币数 days(4) =  k(k+1)/2 = 4*5/2 = 10
0(n) = 1+ 2^2 + 3^2 + 4^2 + ... n^2 

int days( int k ) {        //（递归）返回类型 int 函数名字days int k 参数表  
    if ( k==1 ) return 1;
    return days(k-1)+k;
}

<参数表> = 类型 名字
类型 C         整形、浮点、指针、void
     C++       整形、浮点、指针、引用

递归的方法主要用来找出规律，形成公式，以便直接引用公式计算结果。

答案1

#include <iostream>

int main() { 
    int k, n, num, days; 
    scanf("%d", &n); 
    for( k=1 ; ; k++ )(
        days += k;
        num +=k*(k+1)/2   //或k*k
        if ( days>=n ){
            num -=(days-n)*k;
            break;
        }
    }
    printf("%d\n", num);
    return 0;
}

答案2

#include <iostream>

int main() {
    int n;
    scanf("%d", &n);

    int days = 0, num = 0;
    for(int k=1;;k++) {            //以加的金币数k做循环；
        days += k, num += k*k;     //每阶段结束时的天数days为上次一次结束时的天数+k; k*k 为这一轮可获得总金币数；
        if(days >= n) {            //如果天数>=给定天数，
            num -= (days-n)*k;     //则总量需要扣除，此此轮结束时的天数与指定天数n的差额天数得到的金币数；
            break;                   //这种条件下退出循环。
        }
    }
    printf("%d\n", num);
    return 0;
}