每日一题01、02

斐波那契凤尾

题目描述

NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。

输入描述:

输入有多组数据。
每组数据一行，包含一个整数n (1≤n≤100000)。

输出描述:

对应每一组输入，输出第n个斐波那契数的最后6位。

示例

输入
1
2
3
4
100000
输出
1
2
3
5
537501

第 1 2 3 4 5…
V[] 0 1 2 3 4 5…
数 1 1 2 3 5 8…

代码：

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

int main()
{
    vector <int> v;
    v.push_back(1);
    v.push_back(2);
    for(int i=2;i<100000;i++)
    {
        v.push_back(0);
        v[i]=(v[i-1]+v[i-2])%1000000;
    }
    int n=0;
    while(cin>>n)
    {
        if(n<31)
            cout<<v[n-1]<<endl;
        else
            cout<<setw(6)<<setfill('0')<<v[n-1]<<endl;
    }
    return 0;
}

淘宝网店

题目描述

NowCoder在淘宝上开了一家网店。他发现在月份为素数的时候，当月每天能赚1元；否则每天能赚2元。
现在给你一段时间区间，请你帮他计算总收益有多少。

输入描述:

输入包含多组数据。
每组数据包含两个日期from和to (2000-01-01 ≤ from ≤ to ≤ 2999-12-31)。
日期用三个正整数表示，用空格隔开：year month day。

输出描述:

对应每一组数据，输出在给定的日期范围（包含开始和结束日期）内能赚多少钱。

示例

输入
2000 1 1 2000 1 31
2000 2 1 2000 2 29
输出
62
29

2、3、5、7、11月算一天，其它七月算两天。针对日期计算器，会将其分为三部分进行实现：
1)不足一年的年份
2)最后一年不足一年的年份
3)中间足年的年份。
足年年份只需判断平闰年区别365、366即可。针对情况一不足年年份需要求出该天是该年的第几天，在判断概念平闰情况，用365、366减去前天数即可。也顺便将情况三也解决了。函数实现即可。

代码

#include <iostream>
#include <cmath>
using namespace std;

// 闰年判断，是闰年返回1，不是返回0
int LeapYear(int year) {
    return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
}

// 足年天数
int FullYear(int year) {
    return 2 * 31 + 1 * 28 + 1 * 31 + 2 * 30 + 1 * 31 + 2 * 30 + 1 * 31 
         + 2 * 31 + 2 * 30 + 2 * 31 + 1 * 30 + 2 * 31 + LeapYear(year);
}

// 判断该月是否为素数月
bool suMonth(int n) {
    return n == 2 || n == 3 || n == 5 || n == 7 || n == 11;
}

// 求解当日为一年第几天
int DaysYear(int year, int month, int day) {
    if (!suMonth(month))
        day *= 2;
    while (-- month) {
         switch(month) {   //偶数31天         
             case 1:            
             case 8:            
             case 10:            
             case 12:                
                 day += 62;                
                 break;            
             case 3:        //奇数31天    
             case 5:            
             case 7:                
                 day += 31;                
                 break;            
             case 4:            //偶数30天
             case 6:            
             case 9:                
                 day += 60;                
                 break;            
             case 11:             //奇数30天   
                 day += 30;                
                 break;            
             case 2:             //2月单独看   
                 day += 28 + LeapYear(year);                
                 break;            
             default:;        
         }    
    }    
    return day; 
}

int main() {
    int year1, month1, day1, year2, month2, day2;
    int count = 0;
    while (cin >> year1 >> month1 >> day1 >> year2 >> month2 >> day2) {
        count = 0;
        // 这里day1 - 1可能出现0日，但如2月0日即为1月31日，不影响结果
        count += FullYear(year1) - DaysYear(year1, month1, day1 - 1);
        count += DaysYear(year2, month2, day2);
        if (year1 == year2) 
            count -= FullYear(year1);
        for (int i = year1 + 1; i < year2; ++i) 
            count += FullYear(i);
        cout << count << endl;
    }
    return 0;
}

861 美国节日

题目描述

和中国的节日不同，美国的节假日通常是选择某个月的第几个星期几这种形式，因此每一年的放假日期都不相同。具体规则如下：
1月1日：元旦
1月的第三个星期一：马丁·路德·金纪念日
2月的第三个星期一：总统节
5月的最后一个星期一：阵亡将士纪念日
7月4日：美国国庆
9月的第一个星期一：劳动节
11月的第四个星期四：感恩节
12月25日：圣诞节
现在给出一个年份，请你帮忙生成当年节日的日期。

输入描述:

输入包含多组数据，每组数据包含一个正整数year（2000≤year≤9999）。

输出描述:

对应每一组数据，以“YYYY-MM-DD”格式输出当年所有的节日日期，每个日期占一行。
每组数据之后输出一个空行作为分隔。

示例

输入
2014
2013
输出
2014-01-01
2014-01-20
2014-02-17
2014-05-26
2014-07-04
2014-09-01
2014-11-27
2014-12-25
2013-01-01
2013-01-21
2013-02-18
2013-05-27
2013-07-04
2013-09-02
2013-11-28
2013-12-25

蔡勒公式：

w是计算出的星期；
c是世纪，其值为真实的世纪数-1，也就是y / 100的结果；
y是这是这个世纪的第几年，也就是y % 100；
m是月，但是1月和2月要看做13月和14月计算；
d是日。
根据泰勒公式，我们只需要知道年月日，就可以算出星期。

我们发现，如果所求星期数比1号星期数大，那么直接相减后+1就是那一天了。
例如1号周三，我要周五，那么(5-3)+1即可求出第一个周五是3号。
那么反过来是所求星期数小。
例如1号周三，我要周一，那么显然要先把周一看成周八才行。也就是(8-3)+1。第一个周一是6号。
但是这样要判断，所以干脆统统都让它加7以后减，减完后的结果再mod一下7，就能得到结果了。也就是：(所求星期数 + 7 - 1号星期数) % 7 + 1。这样我们就拿到了求第一个周几公式。随后，我们只需要在这个公式上，加上7 * (n - 1)，即刻求出第n个周几。

代码：

#include <iostream>
#include <cstdio>

// 根据 年-月-日 通过蔡勒公式计算当前星期几
// 1: 星期一 ... 7: 星期日
int day_of_week(int year, int month, int day)
{
   if (month == 1 || month == 2)
   {
     month += 12;
     year -= 1;
   }
   
   int century = year / 100;
   year %= 100;
   int week = year + (year / 4) + (century / 4) - 2 * century + 26 * (month + 1) / 10 + day -1;//蔡勒公式
   week = (week % 7 + 7) % 7;//蔡勒公式
   
   if (week == 0)
   {
     week = 7;
   }
   
   return week;
}

int day_of_demand(int year, int month, int count, int d_of_week)
{
   int week = day_of_week(year, month, 1); //求出1号星期数
   // 1 + 7(n - 1) + (所求星期数 + 7 - 1号星期数) % 7
   int day = 1 + (count - 1) * 7 + (7 + d_of_week - week) % 7;
   return day;
}

// 元旦
void new_year_day(int year)
{
   printf("%d-01-01\n", year);
}
// 马丁·路德·金纪念日（1月的第三个星期一）
void martin_luther_king_day(int year)
{
   printf("%d-01-%02d\n", year, day_of_demand(year, 1, 3, 1));
}
// 总统日（2月的第三个星期一）
void president_day(int year)
{
   printf("%d-02-%02d\n", year, day_of_demand(year, 2, 3, 1));
}
// 阵亡将士纪念日（5月的最后一个星期一）
void memorial_day(int year)
{
   // 从 6 月往前数
   int week = day_of_week(year, 6, 1);
   // 星期一的话，从 31 号往前数 6 天，否则，数 week - 2 天
   int day = 31 - ((week == 1) ? 6 : (week - 2));
   printf("%d-05-%02d\n", year, day);
}
// 国庆
void independence_day(int year)
{
   printf("%d-07-04\n", year);
}
// 劳动节（9月的第一个星期一）
void labor_day(int year)
{
   printf("%d-09-%02d\n", year, day_of_demand(year, 9, 1, 1));
}
// 感恩节（11月的第四个星期四）
void thanks_giving_day(int year)
{
   printf("%d-11-%02d\n", year, day_of_demand(year, 11, 4, 4));
}
// 圣诞节
void christmas(int year)
{
printf("%d-12-25\n", year);
   }
// 美国节日
void holiday_of_usa(int year)
{
   new_year_day(year);
   martin_luther_king_day(year);
   president_day(year);
   memorial_day(year);
   independence_day(year);
   labor_day(year);
   thanks_giving_day(year);
   christmas(year);
}

int main()
{
   int year;
   while (std::cin >> year)
   {
     holiday_of_usa(year);
     putchar('\n');
   }
}

分解因数

题目描述

所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × … × an,并且 1 < a1 ≤ a2 ≤ a3 ≤ … ≤ an。其中a1、a2、…、an均为素数。 先给出一个整数a，请输出分解后的因子。

输入描述:

输入包含多组数据，每组数据包含一个正整数a（2≤a≤1000000）。

输出描述:

对应每组数据，以“a = a1 * a2 * a3…”的形式输出因式分解后的结果。

示例

输入
10
18
输出
10 = 2 * 5
18 = 2 * 3 * 3

我们需要用质数去试除。90能被2整除，那就拿商继续除以2，除不尽就换3，一直到除到质数为止。

代码

#include <cstdio>
#include <cmath>
#include <iostream>

int main()
{
   int n;
   
   while (std::cin >> n)
   {
     printf("%d =", n); //输出90 =
     
     for (int i = 2; i <= std::sqrt(n); i++)
     {
       while (n % i == 0 && n != i) //反复除同一个数，直到除不尽，排除刚好是该数的n次方的情况
       {
       printf(" %u *", i); //第一次打印 2 *,第二次打印两个 3 *
       n /= i; //能整除就修改n的值
       }
     }
     
     printf(" %d\n",n); //跳出后，n已经是处理过的一个质数，就是最后一个质因数：5
   }
   
return 0;
}