5

我是编程和 Java 的新手，我正在尝试通过 Project Euler 网站自学。我正在尝试解决这个问题：http://projecteuler.net/problem=19，即：

在 20 世纪（1901 年 1 月 1 日至 2000 年 12 月 31 日）有多少个星期日是每月的第一天？

我想解决它的方法是制作一个表示压延机的二维数组，并通过数到 7 来循环遍历数组，然后每次数到 7 时，在数组中的那个点上加 1。最后，我将对数组的第一行求和，这应该是每月第一天有多少个星期日。

但是我的循环有问题，到月底时我的计数重置为 7，我不知道如何阻止它这样做？

这是我的代码：

public class Problem019 {
    public static void main (String[] args){

        //System.out.println(LeapYearTest(1996));
        int ThirtyOne = 31;
        int Thirty = 30;
        int FebNorm = 28;
        int FebLeap = 29;
        int a, b, c, Day, e = 0, f = 0;
        int Calander[] []= new int [12] [] ;

        Calander[0] = new int [ThirtyOne];
        Calander[1] = new int [FebNorm];
        Calander[2] = new int [ThirtyOne];
        Calander[3] = new int [Thirty];
        Calander[4] = new int [ThirtyOne];
        Calander[5] = new int [Thirty];
        Calander[6] = new int [ThirtyOne];
        Calander[7] = new int [ThirtyOne];
        Calander[8] = new int [Thirty];
        Calander[9] = new int [ThirtyOne];
        Calander[10] = new int [Thirty];
        Calander[11] = new int [ThirtyOne];

        for (a=1901;a<2001;a++){
            //System.out.println(a);
            if (LeapYearTest(a))
            {
                Calander[1] = new int [FebLeap];
            }
            else
            {
                Calander[1] = new int [FebNorm];
            }

            for (e=0;e<Calander.length;e++)
            {   
                System.out.println("e: " + e);
                f=0;

                while (f<Calander[e].length)
                {   

                    //System.out.println(Calander[e].length);
                    Day=1;
                    while (Day<8 && f<Calander[e].length)
                    {   
                        System.out.println("f: " + f + "\tDay: " + Day + "\tCalander[e][f]: " + Calander[e][f]);
                        Day++;
                        f++;

                        if (f<Calander[e].length && f!=0 && Day==7)
                        {
                        Calander[e][f]+= 1;
                        }

                    }

                }
            }
            //System.out.println(a);
        }
        for (b=0;b<Calander.length;b++)
        {   
            System.out.print(Calander[0][b]);
        }
    }   


    public static boolean LeapYearTest(int x)
    {
        if (x%4==0 || x%400==0){
            return true;
        }
        if (x%100==0){
            return false;
        }
        else return false;
    }

}

这是它打印的内容，e 是月份，f 是月份中的天数，Day 数到 7：

f: 25   Day: 5  Calander[e][f]: 0
f: 26   Day: 6  Calander[e][f]: 0
f: 27   Day: 7  Calander[e][f]: 100
f: 28   Day: 1  Calander[e][f]: 0
f: 29   Day: 2  Calander[e][f]: 0
**f: 30 Day: 3  Calander[e][f]: 0**
e: 10
**f: 0  Day: 1  Calander[e][f]: 0**
f: 1    Day: 2  Calander[e][f]: 0
f: 2    Day: 3  Calander[e][f]: 0

如何设置循环以使 Day 不会在月底重置？或者有没有另一种方法来解决这个问题，不涉及这么多嵌套循环？

谢谢！

4

8 回答 8

4

如果有一个将年份从 1901 年增加到 2001 年的外部循环，以及一个检查 Jan -> Dec 的内部循环，然后只查看该月的第一天是否是星期日，会不会快得多？

总共 100 * 12 次迭代，10 行代码，最高。

编辑：对此进行扩展。

您可以通过两种方式解决问题 - 查看所有星期日，看看它们是否在一个月的第一天，或者查看所有月份的第一天，看看它是否是星期日。

未经测试的代码：

Calendar calendar = Calendar.getInstance();
int count = 0;
for(int i=1901;i<2000;i++){
    for(int j=1;i<12;j++){
        calendar.set(Calendar.YEAR, i);
        calendar.set(Calendar.MONTH,j);
        calendar.set(Calendar.DAY,1);
        if(calendar.get(Calendar.DAY_OF_WEEK).equals(Calendar.SUNDAY)){
            count++;
        }
    }
}

System.out.println(count);

于 2012-04-29T08:10:27.393 回答
3

我认为您需要抛弃现有代码并重新开始。由于您正在尝试通过解决 Project Euler 问题来学习如何编码，因此我不会通过给您代码来破坏您的乐趣。看来您确实想要完整的工作代码，所以我已经修复了您的代码，包括由于问题陈述中的一些微妙细节而出现的一些错误，您可能误解或忽略了这些错误。

只是为了好玩，让我们看一下您想要修复的代码的直接问题......

最初声明Day时，将其初始化为 1。然后替换此行：

Day=1;

有了这个：

if (Day > 7) {
    Day = 1;
}

并将其移动到一个月中的循环中。

但是还有一个严重的问题。你每年都会覆盖你的二月数组。您应该只初始化一次，并将其长度设置为 29。但这也有一个不幸的副作用，即破坏任何依赖于 的循环calendar[month].length，因此您也必须考虑到这一点。

您真正需要跟踪的是每月第一天的星期日数，因此您只需要存储和增加一个变量即可。这解决了上述覆盖二月数组的问题，因为您将不再使用它（或任何其他月份的数组）。另一方面，如果你真的只是想练习使用数组，你可以使用一个 3 维数组（其中额外的维度是年份）。但我敢猜测，大多数 Java 程序员大部分时间都使用列表而不是数组，而当他们使用数组时，他们几乎不会使用一维以上的数组。

还有一些注意事项

你的外while循环是多余的。

LeapYearTest对于可被 100 整除的所有闰年，您的方法将错误地返回 true（所有可被 100 整除的年份也可被 4 整除，因此您永远不会进入测试可被 100 整除的年份的 if 块）。

最后，您将在 1 月的每一天循环（而不是在每个月的第一天循环）。

另请注意，问题指出，

1900年1 月 1日是星期一。

但是你应该找到从1901 年1 月 1 日开始的星期日。

在修复了这些和其他错误（例如循环中的条件）之后，我在下面包含了您的代码的完整工作版本。请注意，您可以通过更多地使用模数 (%) 运算符并且不计算该月其他日期的星期日数（因为最终还是将它们扔掉），可以轻松地优化它以在一小部分时间内运行）。

public class Problem019 {
    public static void main (String[] args){

        final int ThirtyOne = 31;
        final int Thirty = 30;
        final int FebNorm = 28;
        final int FebLeap = 29;
        int numOfSundays = 0;

        int calendar[][]= new int [12][];

        calendar[0] = new int [ThirtyOne];
        calendar[1] = new int [FebLeap];
        calendar[2] = new int [ThirtyOne];
        calendar[3] = new int [Thirty];
        calendar[4] = new int [ThirtyOne];
        calendar[5] = new int [Thirty];
        calendar[6] = new int [ThirtyOne];
        calendar[7] = new int [ThirtyOne];
        calendar[8] = new int [Thirty];
        calendar[9] = new int [ThirtyOne];
        calendar[10] = new int [Thirty];
        calendar[11] = new int [ThirtyOne];

        int dayOfWeek = 1;
        for (int year = 1900; year < 2001; year++) {
            for (int month = 0; month < calendar.length; month++) {   
                int dayOfMonth=0;

                int daysInMonth;
                if (month == 1) {
                    daysInMonth = isLeapYear(year) ? FebLeap : FebNorm;
                }
                else {
                    daysInMonth = calendar[month].length;
                }

                while (dayOfWeek < 8 && dayOfMonth < daysInMonth) {   
                    System.out.println("year: " + year + "\tday: " + dayOfWeek
                            + "\tcalendar["+month+"]["+dayOfMonth+"]: " + calendar[month][dayOfMonth]);

                    if (dayOfWeek == 7 && year > 1900) {
                        calendar[month][dayOfMonth]++;

                        if (dayOfMonth == 0) {
                            numOfSundays++;
                        }
                    }

                    dayOfMonth++;

                    dayOfWeek++;
                    if (dayOfWeek > 7) {
                        dayOfWeek=1;
                    }
                }
            }
        }

        for (int month = 0; month < calendar.length; month++) {   
            System.out.println(calendar[month][0]);
        }

        System.out.println(numOfSundays);
    }   

    public static boolean isLeapYear(int year){
        if (year % 400 == 0) {
            return true;
        }
        else if (year % 100 == 0) {
            return false;
        }
        else if (year % 4 == 0){
            return true;
        }
        else {
            return false;
        }
    }
}

同样，这可以改进很多。例如，您可以简单地循环年份和月份，并使用 Java 内置的 Calendar API 或第三方 API 来检查该月的第一天是否是星期日，但这可能是解决问题的最酷方法就是自己实现末日算法。这将允许您轻松计算任何给定日期的星期几，而无需使用 java.util.Calendar。

一旦你实现了世界末日算法，你不必每次都循环所有的月份，所以你可以做更多的优化。例如，isSunday(MAR,1,year)== (! isLeapYear(year)) && isSunday(FEB,1,year)。

于 2012-04-29T09:06:58.470 回答
1

这是我的提议。它使用公历来识别日期，然后确定是星期天。

import java.util.Date;
import java.util.GregorianCalendar;

public class SundayOfXX {

    public static void main(String [] argv) {
        int counter = 0;
        for (int year = 1901, last_year = 2000; year <= last_year ; year++) {
            for (int month = 1, last_month = 12; month <= last_month ; month++) {
                Date d = new GregorianCalendar(year,month-1,1).getTime(); // GregorianCalendar use 0 for January
                if (d.getDay() == 0) { // sunday is day number 0
                    counter++;
                    System.out.println(String.valueOf(counter) + " " + d);
                }
            }
        }
        System.out.println("Total sunday in XX century: "+counter);
    }
}

此解决方案经过全面测试。它找到了 20 世纪一个月的第一天的 171 个星期日。

于 2012-04-29T08:26:41.167 回答
1

试试这个：

import java.util.Calendar;
public class Problem019 {   

    public static void main (String[] args){

        Calendar calendar = Calendar.getInstance();
        int countFirstSunday = 0;
        for(int year = 1901; year <= 2000 ; year++) {
            for(int month = 0; month <= 11; month++) {
                calendar.set(year, month, 1);
                if(calendar.get(Calendar.DAY_OF_WEEK) == Calendar.SUNDAY) {
                    countFirstSunday++;
                }
            }
        }
        System.out.println("Sundays as the first of month: " + countFirstSunday);
    }

}
于 2012-04-29T09:23:19.053 回答
0

这是您清理和简化的代码：

public static void main(String[] args) {
  final int thirtyOne = 31, thirty = 30;
  final int calendar[][] = new int[12][];
  final int[] febLeap = new int[29];
  final int[] febNorm = new int[28];
  calendar[0] = new int[thirtyOne];
  calendar[2] = new int[thirtyOne];
  calendar[3] = new int[thirty];
  calendar[4] = new int[thirtyOne];
  calendar[5] = new int[thirty];
  calendar[6] = new int[thirtyOne];
  calendar[7] = new int[thirtyOne];
  calendar[8] = new int[thirty];
  calendar[9] = new int[thirtyOne];
  calendar[10] = new int[thirty];
  calendar[11] = new int[thirtyOne];
  int dow = 0; // set to day of week for Jan 1 1901
  for (int y = 1901; y < 2001; y++) {
    calendar[1] = leapYearTest(y)? febLeap : febNorm;
    for (int m = 0; m < calendar.length; m++)
      for (int d = 0; d < calendar[m].length; d++)
        if (dow++ % 7 == 0) calendar[m][d]++;
  }
  int sumSundays = calendar[0][0] + febLeap[0] + febNorm[0];
  for (int i = 2; i < calendar.length; i++) sumSundays += calendar[i][0];
  System.out.println("Number of Sundays is " + sumSundays);
}

public static boolean leapYearTest(int x) {
  if (x % 4 == 0 || x % 400 == 0)
    return true;
  return x % 100 != 0;
}

当我说你不需要数组时，这就是我的意思：

public static void main(String[] args) {
  final int[] mLens = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  int dow = 0; // initialize to day of week on Jan 1, 1901
  int suns = 0;
  for (int y = 1901; y < 2001; y++)
    for (int m = 0; m < mLens.length; m++) {
      if (dow++ % 7 == 0) suns++;
      final int mLen = mLens[m] + leapAdd(y, m);
      for (int d = 1; d < mLen; d++) dow++;
    }
  System.out.println(suns);
}

static int leapAdd(int y, int m) {
  if (m != 1) return 0;
  if (y % 4 == 0 || y % 400 == 0) return 1;
  return y % 100 == 0 ? 0 : 1;
}

但是你马上就会意识到在一个月的几天里运行的内部循环是没有意义的，当它只是模 7 时。所以内部循环应该说

    for (int m = 0; m < mLens.length; m++) {
      if (dow == 0) suns++;
      final int mLen = mLens[m] + leapAdd(y, m);
      dow = (dow + mLen) % 7;
    }
于 2012-04-29T16:09:18.637 回答
0

我会这样做（伪代码）：

class MyDate { ... } // support adding a number of days and comparing with another MyDate
MyDate end = new MyDate(31. Dec 2000)
MyDate start = new MyDate(first sunday in 20th century)
int count = start.mday == 1 ? 1 : 0;
start.add(7);
while (start < end) (
    if (start.mday == 1) count++;
    start.add(7);
}

请注意，不需要任何数组，更不用说二维数组了。（但是，要获取月份长度，在 MyDate 的 add 方法中，使用简单的常量数组是可以的。）

于 2013-07-18T14:32:40.327 回答
0

这里有2个解决方案：

1）使用Calendar- 它更简单，但效率不高 - 135 ms

import java.util.Calendar;

public class P19 {

    public static void main(String[] args) {
        int result = 0;
        for ( int year = 1901 ; year <= 2000 ; year++ ) {
            for ( int month = Calendar.JANUARY ; month <= Calendar.DECEMBER ; month++ ) {
                Calendar c = getCalendar(year, month, 1);
                if ( c.get(Calendar.DAY_OF_WEEK) == Calendar.SUNDAY ) {
                    result++;
                }
            }
        }
        System.out.println(result);
    }

    private static Calendar getCalendar(int year, int month, int day) {
        Calendar c = Calendar.getInstance();
        c.set(Calendar.YEAR, year);
        c.set(Calendar.MONTH, month);
        c.set(Calendar.DAY_OF_MONTH, day);      // or Calendar.DATE
        return c;
    }

}

请注意：

  • DAY_OF_MONTH并且DATE是等价的。
  • 我使用Calendar.JANUARY是因为第一个月是0，而不是1，即使第一天/日期是1。

2)使用我自己的 Date 课程- 只需1.65 毫秒：

public class P19 {

    public static void main(String[] args) {
        // 1 Jan 1900 - Monday
        // 1900 is not leap => it has 365 days
        // 365 % 7 = 1 => 1 Jan 1901 - Tuesday => 6 Jan 1901 - Sunday

        int yearStart = 1901, yearEnd = 2000;
        int monthStart = 1, monthEnd = 12;
        int dayStart = 6, dayEnd = 31;
        Date dateStart = new Date(yearStart, monthStart, dayStart);
        Date dateStop = new Date(yearEnd, monthEnd, dayEnd);

        int result = 0;
        while (Date.compareDates(dateStart, dateStop) < 0) {
            if (dateStart.day == 1) {
                result++;
            }
            dateStart.addDays(7);
        }
        System.out.println(result);
    }

}

class Date {
    int year;
    int month;
    int day;

    Date(int year, int month, int day) {
        this.year = year;
        this.month = month;
        this.day = day;
    }

    public void addDays(int days) {
        int numberOfDaysForMonth = getTotalMonthDays(month, year);
        day += days;
        if (day >= numberOfDaysForMonth) {
            day -= numberOfDaysForMonth;
            month++;
            if (month > 12) {
                month = 1;
                year++;
            }
        }

    }

    public static int compareDates(Date d1, Date d2) {
        if (d1.year == d2.year && d1.month == d2.month && d1.day == d2.day) {
            return 0;
        }
        if (d1.year < d2.year) {
            return -1;
        }
        if (d1.year == d2.year && d1.month < d2.month) {
            return -1;
        }
        if (d1.year == d2.year && d1.month == d2.month && d1.day < d2.day) {
            return -1;
        }
        return 1;
    }

    private int getTotalMonthDays(int m, int y) {
        if (m == 2 && isLeapYear(y)) {
            return 29;
        }
        if (m == 2) {
            return 28;
        }
        if (m == 4 || m == 6 || m == 9 || m == 11) {
            return 30;
        }
        return 31;
    }

    private boolean isLeapYear(int y) {
        if (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0)) {
            return true;
        }
        return false;
    }

}

此实现仅通过星期日 ( addDays(7)) 进行迭代。

一些可能的改进：

  • 增加步长（例如：对于1，我们可以添加28而不是7跳过任何一天）
  • 更改 compare 方法以返回 aboolean并简化其主体
于 2014-11-21T22:36:48.583 回答
0 
public class CountingSundays {

    public static void main(String[] args) {

        int lastDayOfPreviousMonth = 6; //31 Dec 1899 is Sunday as 1 Jan 1900 is Monday

        int countOfSundayOnFirstOfMonth = 0;

        for (int year = 1900; year <= 2000; year++) {
            for (int month = 1; month <= 12; month++) {
                int dayOnFirstOfThisMonth = (lastDayOfPreviousMonth + 1) % 7;
                if (year > 1900 && dayOnFirstOfThisMonth == 6)
                    countOfSundayOnFirstOfMonth++;
                switch (month) {
                case 1: // Jan
                case 3: // Mar
                case 5: // May
                case 7: // Jul
                case 8: // Aug
                case 10: // Oct
                case 12: // Dec
                    lastDayOfPreviousMonth = (lastDayOfPreviousMonth + 3) % 7;
                    break;
                case 4: // Apr
                case 6: // Jun
                case 9: // Sep
                case 11: // Nov
                    lastDayOfPreviousMonth = (lastDayOfPreviousMonth + 2) % 7;
                    break;
                case 2: // Feb
                    if (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0))
                        lastDayOfPreviousMonth = (lastDayOfPreviousMonth + 1) % 7;
                }
            }
        }


        System.out.println(countOfSundayOnFirstOfMonth);
    }

}
于 2017-06-01T19:28:32.457 回答