坂本智彦のアルゴリズム - 曜日を求める

この記事では、坂本智彦アルゴリズムとは何か、またそれを使用して指定された日付が何曜日であるかを特定する方法について説明します。曜日を知るアルゴリズムはいくつかありますが、このアルゴリズムが最も強力です。このアルゴリズムは、可能な限り短い時間と最小のスペース複雑さで、この日付が発生する月の日付を見つけます。

問題文 - グルジア暦に基づいた日付が与えられ、私たちのタスクは、坂本智彦のアルゴリズムを使用して、指定された日付が何曜日であるかを見つけることです。

＃＃＃例＃＃＃

入力

- 日付 = 30、月 = 04、年 = 2020

出力

- 指定された日付は月曜日です

入力

- 日付 = 15、月 = 03、年 = 2012

出力

- 指定された日付は木曜日です

入力

- 日付 = 24、月 = 12、年 = 2456

出力

- 指定された日付は日曜日です 坂本智彦のアルゴリズム

ここで、坂本智彦のアルゴリズムの背後にある直感について説明しましょう。

ご存知のとおり、グルジアの暦によれば、西暦 1 月 1 日は月曜日になります。

ケース 1 うるう年を無視する

最初に、すべての閏年が無視される場合、つまり 1 年が 365 日である場合について説明します。

1 月は 31 日で、1 週間は 7 日なので、1 月には 7*4 の 3 日があると言えます。つまり、2 月の初日は常に 1 月の初日の 3 日後です。

2 月は 28 日あり (閏年を除く)、これ自体は 7 の倍数なので、3 月 1 日は 2 月 1 日と同じ日になると言えます。つまり、3 月 1 日も 3 1 になります。月の 1 日からの日数。 p>

さて、4 月の場合、3 月は 31 日あり、7*4 3 になります。つまり、3 月 1 日の 3 日後に発生することになります。したがって、4月1日は1月1日の6日後であると言えます。

ここで、arr[i] が 1 月 1 日を基準とした第 i 月以降の追加日数を表す配列を構築します。

arr[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5} となります。

ケース 2 うるう年

次に、うるう年の状況について説明します。

4 年ごとに 1 日が計算に追加されますが、100 年ごとではありません。この余分な日数を考慮する必要があります。これを行うには、式 -

を使用します。

年 / 4 (4 年ごと)

– 年 / 100 (100 年ごとに 4 の倍数ですが、それでも閏年ではないため、閏年から削除します)

年 / 400 (400 年ごと、100 の倍数ですが、繰り返しの年です)

この式により、正確な閏年数が得られます。ただし、例外が 1 つあります。

これで、1 月 0 日ではなく、2 月 29 日が閏日とみなされます。

これは、うるう日は影響しないため、年の最初の 2 か月を計算に含める必要がないことを意味します。したがって、1 月または 2 月の場合は、年から 1 を引いて補正します。したがって、これらの月では、year/4 の値は今年ではなく前年に基づく必要があります。

うるう年の問題を解決するには、2 月以降の各月の arr[] 値から 1 を引いてギャップを埋めることができます。これでうるう年の問題は解決します。閏年と平年の両方で機能するように、アルゴリズムに次の変更を加える必要があります。

arr[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 }

現在の月が 1 月または 2 月の場合、年から 1 を引く必要があります。

モジュラスの年の増分を、年の代わりに年/4 –年/100年/400に変更する必要があります。この変更は、うるう年の余分な日を考慮し、それに応じて計算を調整するために必要です。

＃＃＃例＃＃＃

このメソッドのコードは次のとおりです:

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃複雑＃＃＃

時間計算量 - このメソッドの時間計算量は O(1)

です。

空間の複雑さ - 余分な空間を使用していないため、このアプローチの空間の複雑さは O(1) です。

結論

- この記事では、坂本智彦のアルゴリズムとその背後にある直感について説明しました

以上が坂本智彦のアルゴリズム - 曜日を求めるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。