C语言之打鱼晒网问题

目录

一 简介

二 代码实现

步骤一：判断输入日期

步骤二：计算总天数

步骤三：判断行为模式

三 时空复杂度

---

一 简介

打鱼晒网问题是一个经典的编程题目，源自中国的俗语“三天打鱼两天晒网”，意思是周期性地工作和休息。在C语言中实现这一问题的程序设计目标是：当给定一个日期后，计算出从某一固定起始日（如1990年1月1日或2011年1月1日）开始到该日期为止，渔夫按照每连续五天循环一次的行为模式（前三天打鱼，后两天晒网），确定在给定日期渔夫是在打鱼还是晒网。

二 代码实现

以下是解决此问题的基本步骤：

步骤一：判断输入日期

首先，需要获取用户输入的日期或者通过函数参数接收日期，并将其分解为年、月、日三个部分。

步骤二：计算总天数

编写一个函数来计算从固定起始日期到给定日期之间的总天数。这通常包括以下子步骤：

• 判断输入年份是否为闰年。
• 根据年份和平/闰年的不同，计算各年内每月的天数累计值。
• 累加对应年份、月份以及日期的天数，得到总天数。

例如，可以使用类似于上述提及的方法计算自2011年1月1日以来的总天数，其中涉及到判断是否为闰年，以及根据不同的年份类型（平年或闰年）累加每个月的天数。

步骤三：判断行为模式

将计算出的总天数对5取余数，因为每5天是一个完整的循环周期：

• 如果余数是1、2或3，则表示渔夫在这一天应该打鱼。
• 如果余数是0或4，则表示渔夫在这一天应该晒网。

#include <stdio.h>
 
// 定义判断是否为闰年的函数
int is_leap_year(int year) {
    if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
        return 1;
    else
        return 0;
}
 
// 计算从指定年份开始到输入日期的总天数
int calculate_total_days(int start_year, int start_month, int start_day,
                        int input_year, int input_month, int input_day) {
    // 这里应该填充具体的计算逻辑，考虑闰年和平年的区别
    // ...
}
 
int main() {
    int start_year = 2011, start_month = 1, start_day = 1;
    int input_year, input_month, input_day;
 
    // 获取用户输入的日期
    // ...
 
    // 计算总天数
    int total_days = calculate_total_days(start_year, start_month, start_day,
                                         input_year, input_month, input_day);
 
    // 判断行为模式
    int remainder = total_days % 5;
    
    if (remainder == 1 || remainder == 2 || remainder == 3) {
        printf("渔夫在这一天打鱼。\n");
    } else if (remainder == 0 || remainder == 4) {
        printf("渔夫在这一天晒网。\n");
    }
 
    return 0;
}

请注意，以上代码示例仅展示了基本思路和结构，并未提供完整的calculate_total_days函数实现细节，实际编程时需要根据具体日期算法填充这部分内容。

三 时空复杂度

上述代码中未提供calculate_total_days函数的具体实现，因此无法精确分析整个算法的时间复杂度和空间复杂度。不过，我们可以大致推测：

1. 时间复杂度：

   • is_leap_year函数的时间复杂度为O(1)，因为它仅包含一次条件判断。
   • 对于calculate_total_days函数，其时间复杂度取决于具体实现。如果采用逐日累加的方式计算总天数，则最坏情况下（例如从公元元年到目标日期）时间复杂度为O(n)，n表示经过的天数。但如果使用更高效的算法（如Zeller's congruence或直接查找预计算好的表），则可以降低至近乎O(1)。

2. 空间复杂度：

   • 整个程序中没有使用额外的数据结构来存储大量数据，主要使用的变量都是局部变量，因此空间复杂度为O(1)。

在实际编程中，为了提高效率，我们通常会避免逐日累加计算天数，而是利用一些数学公式或者预计算好的日历表来快速定位输入日期与起始日期之间的天数差。这样的优化可以显著降低时间复杂度，提升程序性能。