63

坂本のアルゴリズムを使用して、特定の日付から曜日を見つけています。このアルゴリズムの正しさを教えてもらえますか? 2000年から2099年までこれが欲しいだけです。

ウィキペディアのアルゴリズムを参照用に示します。

int dow(int y, int m, int d)
{
   static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
   y -= m < 3;
   return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}
4

4 に答える 4

130

まあ、それを見るだけで正しいことがわかります...配列が正しいと仮定すると、t[]たった12回のスポットチェックで確認できます(任意の日/年を使用して毎月1回)。

これy -= m < 3はいいトリックです。3 月 1 日に開始し、2 月 28 日 (または 29 日) に終了する「仮想年」を作成し、余分な日 (ある場合) を年末に置きます。というか、昨年末。たとえば、仮想年 2011 は 3 月 1 日に始まり、2 月 29 日に終了しますが、仮想年 2012 は 3 月 1 日に始まり、翌 2 月 28 日に終了します。

仮想年の終わりに閏年の追加日を置くことで、残りの式は大幅に簡素化されます。

合計を見てみましょう：

(y + y/4 - y/100 + y/400 + t[m-1] + d) % 7

通常、1 年は 365 日です。つまり、52 週プラス 1 日です。そのため、一般的に、曜日は 1 年に 1 日ずれます。それがこのy用語が貢献しているものです。年ごとに 1 日が加算されます。

しかし、4 年に一度は閏年です。これらは、4 年ごとに 1 日余分に貢献します。仮想年を使用するおかげでy/4、合計に追加するだけで、うるう日の数を数えることができyます。(この式は、整数除算が切り捨てられることを前提としていることに注意してください。)

しかし、100 年ごとは閏年ではないため、これは正しくありません。したがって、 off を減算する必要がありますy/100。

ただし、400 年ごとに再びうるう年になります。したがって、追加する必要がありy/400ます。

最後に、日付と、月dに依存するテーブルからのオフセットを追加するだけです (1 年内の月の境界はかなり恣意的であるため)。

次に、1 週間の長さは mod 7 です。

(たとえば、週が 8 日の場合、この数式で何が変わるでしょうか? 明らかに mod 8 になります。また、365 % 8 == 5 であるため、yも である必要があります。また、月の表も調整する必要があります。それでおしまい。）5*yt[]

ちなみに、カレンダーが「9999年まで有効」というウィキペディアの記述は、完全に恣意的なものです。この式は、10 年、100 年、1000 年、100 万年など、グレゴリオ暦に固執する期間に適しています。

[編集]

上記の議論は本質的に帰納法による証明です。つまり、式が特定の (y,m,d) に対して有効であると仮定すると、(y+1,m,d) および (y,m,d+1) に対して有効であることを証明できます。(ここで、y は 3 月 1 日から始まる「仮想年」です。) 重要な問題は、ある年から次の年に移動するときに合計が正しい量だけ変化するかどうかです。うるう年のルールを知っていて、「仮想年」が年末に余分な日を持っていれば、それは自明です。

于 2011-06-17T12:46:50.133 に答える
4

最近、このアルゴリズムに関するブログ投稿をここに書きました。

アルゴリズムの背後にある基本的な考え方は、2 月と 1 月の曜日を前年の 12 月 31 日から数えることです。他のすべての月については、現在の年の 12 月 31 日から曜日をカウントします。これを 2 つのステップで行います。まず、現在の月の前の月の最終日の曜日を計算し、モジュロ 7mを加算します。d

紀元前 1 年 12 月 31 日は 0 としてエンコードされた日曜日で、月曜日は 1 などです。つまり、次のようになります。0 + y + y/4 - y/100 + y/400これはy -= m < 3、今年または前年の 12 月 31 日の曜日を計算します (月によって異なります)。注:これは、の代わりに365 % 7 == 1書いた理由を説明しています。前月の最終日から曜日のカウントを開始するため、最後のコンポーネントは明らかです。y365*yd

説明が必要な最後の部分は、配列の値です。最初の 2 つの値は、昨年の 12 月 31 日から月の始まりまでの日数% 7です。それ以外の月については、前月末から今年の 12 月 31 日までの7 を法とする日数で否定されます。言い換えれば、モジュロ 7 の加算によって日を減算しています(a-b)%7 = (a+(7-b%7))%7。

詳細については、私のブログ投稿を参照してください。

于 2016-06-18T17:38:39.427 に答える