算法题每日一练---第18天：回家路费

一、问题描述

小明被不明势力劫持。后莫名其妙被扔到 X 星站再无问津。小明得知每天都有飞船飞往地球，但需要 108 元的船票，而他却身无分文。

他决定在 X 星战打工。好心的老板答应包食宿，第 1 天给他 1 元钱。 并且，以后的每一天都比前一天多 2 元钱，直到他有足够的钱买票。 请计算一下，小明在第几天就能凑够 108 元，返回地球。

二、题目要求

考察

数学思想，循环条件判断
建议用时2~10min

三、问题分析

问题是第一天是1元，从第一天往后开始计算，每一天都比前一天增加2，最后计算出在第几天能够凑够108元。

对每一天增加的路费使用变量k单独存储，而天数通过for循环实现，当累积的路费到达108，输出当前for循环的天数，退出循环。

拓展：对于本问题来说，可以把路费的增加规律和斐波那契数列相结合，第一天是1，第二天是1，第三天是2，第四天是3......以此类推，直到求出结果。

intfac(intn)//定义函数{
if(n==1||n==2)  return1;//如果天数是1或者2，返回1elsereturnfac(n-1)+fac(n-2);//天数大于2，当前路费等于前两天相加}

四、编码实现

#include<iostream>usingnamespacestd;
intmain()
{
inti,j,sum=108,ans=0,k=1;//初始化定义 for(i=1;;i++)//for循环     {
ans+=k;//对路费计算 if(ans>=sum)//满足条件         {
cout<<i;//输出结果 exit(0);//退出for循环         }
k=k+2;//路费更改     }
return0;
}

五、输出结果

输出结果为：11