曜日を見つけるためのサカモトのアルゴリズムの正しさ

Question

指定された日付から曜日を見つけるために、Sakamoto のアルゴリズムを使用しています。誰かこのアルゴリズムの正しさを教えてもらえますか?これは 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;
}

Answer 1

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

y -= m < 3は素晴らしいトリックです。 3月1日から2月28日（または29日）に終了する「仮想年」を作成し、その年の終わりに余分な日（ある場合）を配置します。というか、前の年の終わりに。たとえば、仮想年2011は3月1日に始まり、2月29日に終了しますが、仮想年2012は3月1日に始まり、次の2月28日に終了します。

うるう年の追加日を仮想年の終わりに置くことにより、式の残りの部分が大幅に簡略化されます。

合計を見てみましょう： ジェネラコディセタグプレ

通常の年は365日です。それは52週間プラス1日です。したがって、一般的に、曜日は1年に1日ずつシフトします。それがy用語が貢献しているものです。毎年1日追加されます。

しかし、4年ごとがうるう年です。それらは4年ごとに1日余分に貢献します。仮想年の使用のおかげで、総和にy/4を追加するだけで、y年に発生するうるう日数を数えることができます。 （この式は整数の除算をダウンすることを前提としていることに注意してください。）

しかし、100年ごとがうるう年ではないため、それは正しくありません。したがって、y/100を差し引く必要があります。

400年ごとが再びうるう年であることを除いて。したがって、y/400を追加する必要があります。

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

それから、1週間の長さなので、mod7のすべてを取ります。

（たとえば、週が8日だった場合、この式はどう変わるでしょうか。もちろん、mod 8になります。また、365％8== 5であるため、yは5*yである必要があります。月もテーブルt[]を調整する必要があります。それだけです。）

ちなみに、カレンダーが「9999まで有効」であるというウィキペディアの声明は完全に恣意的です。この式は、10年、100年、1000年のいずれであっても、グレゴリオ暦を使い続ける場合に適しています。年、または100万年。

[編集]

上記の議論は本質的に帰納法による証明です。つまり、数式が特定の（y、m、d）で機能すると仮定すると、（y + 1、m、d）と（y + 1、m、d）で機能することを証明します。 y、m、d + 1）。 （yは3月1日から始まる「仮想年」です。）重要な質問は、ある年から次の年に移動するときに、合計が正しい量だけ変化するかどうかです。うるう年のルールを理解し、年末に余分な日がある「仮想年」を使用すると、簡単に実行できます。

Answer 2

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

アルゴリズムの背後にある基本的な考え方は、2月と1月に日を数えることです 前年の12月31日からの週。他のすべての月については、12月31日現在からの曜日をカウントします。これは2回で行います。 最初に、現在の月の前月の最終日の曜日を計算し、次に、7を法としてmを追加します。

31 Dec 1 BCは0としてエンコードされる日曜日、月曜日は1などです。 したがって、次のようになります。dthiswith 0 + y + y/4 - y/100 + y/400computes 今年または前年の12月31日の曜日（月によって異なります）。注：y -= m < 3これは、365 % 7 == 1の代わりにyを記述した理由を説明しています。最後のコンポーネントの365*yは、前月の前日から曜日のカウントを開始するため、明らかです。

説明が必要な最後の部分は配列内の値です。最初の2つの値は、昨年12月31日から月の初めまでの日数です。d。残りの月については、前月の終わりから現在の年の12月31日までの日数を 7を法として否定します。言い換えれば、7を法として加算することで日数を減算しています。 % 7。

私のブログ投稿に詳細な説明があります。

Answer 3

これは上記のような完全な答えではないかもしれませんが、この配列に関して1つだけ追加したいと思います：0 3 2 5 0 3 5 1 4 6 2 4

他の人が言ったように、3月から2月までの月を検討してください。

1. 3月
2. 4月
3. 5月
4. 6月
5. 7月
6. 8月
7. 9月
8. 10月
9. 11月
10. 12月
11. 1月
12. 2月

    上記の番号付けスタイルから1月から12月まで書く：

    したがって、これを配列と見なします。 int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

    配列内のすべての要素について、次のようにします：(2.6*m - 0.2) mod 7 結果を整数として解析すると、次のようになります。 0 3 2 5 0 3 5 1 4 6 2 4

    • この式は次の場所にあります：ウィキペディア ジェネラコディセタグプレ

      これ：+ y/4 - y/100 + y/400はうるう年に関連しています。うるう年を確認するためのアルゴリズムは次のとおりです：

      1. 400で完全に割り切れる-> 真
      2. 100で完全に割り切れるが400では割り切れない場合-> 誤り
      3. 4で割り切れる-> 真

         上記の順序でチェックを実行します。たぶんそれが彼らがy / 100を引き、y / 4とy / 400を足した理由です。うんばかげた論理

Answer 4

グレゴリオ暦の場合

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

説明：

• コメントされた配列を参照してください。

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

そしてそれを一年のカレンダーと比較してください（実行 cal 2Linux/UNIX のターミナルでカレンダーを生成する場合)、各月の週の開始日を確認します。

• 通常の年は週の 1 日をずらし、閏年は週の 2 日をずらします。(365%7)=1 および (366%7)=2 として

 i= y+y/4-y/100+y/400

• ただし、y が月 0 と月 1 で閏年の場合は、余分な日を計算すべきではありません。

y-=m<3

• しかし、この方法により、うるう年以外の年からも余分な日が削除されます。したがって、2 月以降の各月で 1 日を減算してギャップを埋めます。

  int t[12]={0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};