国王骑士金币问题

本文以模拟算法的两种方式解题，同时附录递归算法（不建议使用）。

国王发放金币给骑士，按天数发。

分组模拟：

IO

输入天数n，输出金币总数res

循环 （按天数执行）

确定天数n>0的时候执行发放金币，故使用while循环

循环中代表每天发金币的操作，所以循环中包含n的变化

分组 （按每天金币的数量）

可以观察到，在连续k天中发放k枚金币

包含可分组与不可分组

代码C++:

    while(n>0){
        if(n>=k){       
            n-=k;       
            result+=k*k;
        	k++;
        }else{
            result+=k*n;
            n-=k;        
        }          
    }

完整代码

C++

#include<bits/stdc++.h>
using namespace std;
int main(){
//	天数，输入数 
    int n;
    cin >> n
//    每天给的金币数，从1开始模拟 
    int k=1;          //1
//    金币总数，从0开始模拟 
    int result=0;
    while(n>0){
//    	k金币数同时表示发放该k数金币的天数，k天发放k^2枚金币 
        if(n>=k){       //2
//        天数与金币数的关系就是连续1天发1个，连续2天，发2个；连续3天，发3个 
//        如果n天数大于金币数。 
            n-=k;       //3 
            result+=k*k;
        	k++;
        }else{
            result+=k*n;
            n-=k;         //4
        }          //5
    }
    
    cout << result;
    return 0;
}

Python：

# -*- coding: utf-8 -*-

# 输入天数n
# 输出res
n=int(input("输入天数"))
res=0
# 按天数发金币的初始值为1
k=1

while n>0:
    # 执行按天发金币
    # 分组

    if n>=k:
        # 可分组
        res+=k*k
        # 剩余天数的变化
        n-=k
        # 每组金币递增
        k+=1
    else:
        res+=k*n
        n=0

print("金币总数",res)

天数模拟：

void first(){
		
	int n;
//	输入天数 
	cin >> n;
	
//	模拟天数，从0开始
	int days=0; 
	
//	输出金币数
	int res=0;
	
//	从i=1,从第一天1个金币开始模拟。 无限循环 
	for (int i=1;1;i++){
//		每组一共j天，j最大值等于金币数 
		for(int j=1;j<=i;j++){
//			每天金币数 
			res+=i;
//			模拟天数递增
			days++;
			
			if(days==n){
				cout << "输出金币总量： " << res <<endl;
				
				return;
			}
		}
	}
}

递归算法：

递归算法舍近求远，不建议掌握

#include <iostream>
using namespace std;

//国王骑士与金币问题
//国王第一天给骑士1枚金币
/**
	天数与金币的关系如下
	1,1
	2,2
	3,2
	4,3
	5,3
	6,3
	7,4
	8,4
	9,4
	10,4 
*/ 

//分析可知（（（1）k^2）k^3） k为天数递增数
//递归算法
int recursion(int k,int coins){
	if(k==1){
		coins+=1;
		return coins;
	}else{
		coins+=k*k;
		recursion(k-1,coins);
	}
}

//连续n天给n个金币 
int n_recur(int n,int k){
	if(k<=0){
		return n-1;
	}else{
		n+=1;
		k-=n;
		n_recur(n,k);
	}
}

//n的余数 
int n_recur(int k,int n){
	if(k==1){
		return n-=1;
	}else{
		n-=k;
		n_recur(k-1,n);
	}
}

int main(){
	
	int n;
	cin >> n;
	int k=n_recur(1,n);
	
	cout << " k= " << k << endl;
	
	int remainder=n_recur(k,n);
	
	cout << "分组剩余=" << remainder << endl;
	
	int coins=recursion(k,0);
	
	coins+=remainder*(k+1);
	
	cout << coins;
} 

//递归算法舍近求远，不建议