5

私はプログラミングと Java の初心者で、Project Euler の Web サイトで作業して独学しようとしています。私はこの問題を解決しようとしています: http://projecteuler.net/problem=19、つまり:

20 世紀 (1901 年 1 月 1 日から 2000 年 12 月 31 日まで) の月の最初の日曜日は何回ありましたか?

私がそれを解決するために考えた方法は、カレンダーを表す 2D 配列を作成し、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 年にインクリメントする外側のループと、1 月 -> 12 月をチェックする内側のループを用意して、その月の最初が日曜日かどうかを確認する方がはるかに高速ではないでしょうか?

合計で 100 * 12 回の反復、10 行のコード、トップ。

編集：これを拡張するには。

この問題には 2 つの方法で対処できます。すべての日曜日を調べて月の最初の日かどうかを確認するか、すべての月の最初の日を見て日曜日かどうかを確認します。

テストされていないコード:

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(カウント);

于 2012-04-29T08:10:27.393 に答える
3

既存のコードを捨てて、最初からやり直す必要があると思います。あなたはプロジェクトオイラーの問題を解決することによってコーディングする方法を学ぼうとしているので、私はあなたにコードを与えることによってあなたの楽しみを台無しにすることはありません。完全に機能するコードが必要なようです。誤解したり見落としたりした可能性のある問題ステートメントの微妙な詳細が原因で存在していたいくつかのバグを含め、コードを修正しました。

楽しみのために、修正したいコードの当面の問題を見てみましょう...

最初に宣言するときはDay、1に初期化します。次に、次の行を置き換えます。

Day=1;

これとともに：

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

月の日をまたがるループ内に移動します。

しかし、まだ深刻な問題があります。毎年2月の配列を上書きし続けます。初期化は1回だけで、長さを29に設定する必要があります。ただし、これには、に依存するループを壊すという不幸な副作用もあるcalendar[month].lengthため、それも考慮する必要があります。

本当に追跡する必要があるのは、月の最初に当たった日曜日の数だけなので、1つの変数を格納してインクリメントするだけです。これにより、Feb配列（または他の月の配列）を使用しなくなるため、Feb配列を上書きするという前述の問題が解決されます。一方、本当に配列の使用を練習したい場合は、3次元配列（追加の次元は年）を使用できます。しかし、ほとんどのJavaプログラマーは、ほとんどの場合、配列の代わりにリストを使用し、配列を使用する場合、複数の次元を持つ配列を使用することはほとんどないと思います。

さらにいくつかのメモ

外側のwhileループは冗長です。

メソッドLeapYearTestは、100で割り切れるすべてのうるう年に対して誤ってtrueを返します（100で割り切れるすべての年も4で割り切れるので、100で割り切れる年をテストするifブロックには決して入りません）。

最後に、（毎月1日をループするのではなく）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 世紀の月の 1 日である 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);
}

配列は必要なく、ましてや 2 次元配列は必要ないことに注意してください。(ただし、月の長さを取得するには、MyDate の add メソッドで、単純な定数配列を使用しても問題ありません。)

于 2013-07-18T14:32:40.327 に答える
0

ここに2つの解決策があります：

1)使用Calendar- より単純ですが、それほど効率的ではありません - 135 ミリ秒

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ではなくであるため、使用しました。11

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追加することができます)287
  • を返すように比較メソッドを変更し、booleanその本体を単純化します
于 2014-11-21T22:36:48.583 に答える