Corrección del algoritmo de Sakamoto para encontrar el día de la semana

StackOverflow https://stackoverflow.com/questions/6385190

Pregunta

Estoy usando el algoritmo de Sakamoto para averiguar el día de la semana a partir de una fecha determinada.¿Alguien puede decirme la exactitud de este algoritmo?Sólo quiero esto del 2000 al 2099.

El algoritmo de Wikipedia se da como referencia.

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;
}
¿Fue útil?

Solución

Bueno, con solo mirarlo puedes decir que es correcto...Suponiendo que el t[] La matriz es correcta, lo cual puede verificar con solo 12 verificaciones aleatorias (una por cada mes usando cualquier día/año).

El y -= m < 3 es un buen truco.Crea un "año virtual" que comienza el 1 de marzo y termina el 28 (o 29) de febrero, poniendo el día adicional (si lo hubiera) en el fin del año;o mejor dicho, al final del anterior año.Así, por ejemplo, el año virtual 2011 comenzó el 1 de marzo y finalizará el 29 de febrero, mientras que el año virtual 2012 comenzará el 1 de marzo y finalizará el 28 de febrero siguiente.

Al colocar el día añadido para los años bisiestos al final del año virtual, el resto de la expresión se simplifica enormemente.

Veamos la suma:

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

Hay 365 días en un año normal.Eso son 52 semanas más 1 día.Entonces, el día de la semana cambia un día por año, en general.Eso es lo que el y el término está contribuyendo;añade uno al día de cada año.

Pero cada cuatro años es un año bisiesto.Éstos aportan un día extra cada cuatro años.Gracias al uso de años virtuales, podemos simplemente agregar y/4 a la suma para contar cuantos días bisiestos ocurren en y años.(Tenga en cuenta que esta fórmula supone rondas de división de enteros abajo.)

Pero eso no es del todo cierto, porque cada 100 años no es un año bisiesto.Entonces tenemos que restar y/100.

Excepto que cada 400 años vuelve a ser un año bisiesto.Entonces tenemos que agregar y/400.

Finalmente solo agregamos el día del mes. d y una compensación de una tabla que depende del mes (porque los límites de los meses dentro del año son bastante arbitrarios).

Luego toma todo el mod 7, ya que eso es lo que dura una semana.

(Si las semanas fueran ocho días, por ejemplo, ¿qué cambiaría en esta fórmula?Bueno, sería el mod 8, obviamente.También el y necesitaría ser 5*y, porque 365 % 8 == 5.También la tabla de meses. t[] necesitaría ajuste.Eso es todo.)

Por cierto, la afirmación de Wikipedia de que el calendario es "válido hasta el 9999" es totalmente arbitraria.Esta fórmula es buena por mucho tiempo que sigamos con la Calendario Gregoriano, ya sean 10 años, 100 años, 1000 años o 1 millón de años.

[editar]

El argumento anterior es esencialmente una prueba por inducción.Eso es, asumiendo que la fórmula funciona para un particular (y,m,d), usted probar que funciona para (y+1,m,d) y (y,m,d+1).(Donde y es un "año virtual" que comienza el 1 de marzo). Entonces, la pregunta clave es: ¿la suma cambia en la cantidad correcta a medida que se pasa de un año al siguiente?Con conocimiento de las reglas de los años bisiestos y con el "año virtual" teniendo el día extra al final del año, es trivial.

Otros consejos

Puede que esta no sea una respuesta completa como algunas de las mencionadas anteriormente, pero solo me gustaría agregar una cosa con respecto a esta matriz: 0 3 2 5 0 3 5 1 4 6 2 4

Considere meses que comienzan en marzo y terminan en febrero, tal como dijeron otros:

  1. marzo
  2. Abril
  3. Mayo
  4. junio
  5. julio
  6. agosto
  7. septiembre
  8. Octubre
  9. noviembre
  10. diciembre
  11. enero
  12. febrero

Escribir de enero a diciembre con el estilo de numeración anterior:

Considere esto como una matriz: int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

Ahora, para todos los elementos de la matriz, haga lo siguiente: (2.6*m - 0.2) mod 7 analice el resultado como un número entero y obtendrá esto: 0 3 2 5 0 3 5 1 4 6 2 4 

int dayOfWeek(int d, int m, int y){
  // Months Array
  int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

  // Convert months array
  for (int i = 0; i < 12; i++){
    int ans = t[i] * 2.6 - 0.2;
    t[i] = ans % 7;
  }

  // Continue Algo
  if(m<3)
    y -= 1;

  int day = (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
  return day;
}

esto: + y/4 - y/100 + y/400 está relacionado con el año bisiesto. El algoritmo para verificar el año bisiesto es:

  1. Perfectamente divisible por 400 -> verdadero
  2. SI es perfectamente divisible entre 100 pero no entre 400 -> Falso
  3. Divisible por 4 -> Verdadero

realice comprobaciones en el pedido anterior. Quizás por eso restaron y / 100 y agregaron y / 4 & y / 400. Sí, lógica tonta

Para el calendario gregoriano 

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;
}

Explicación:

  • Ver la matriz comentada para 
 t[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5};

y compárelo con un calendario de un año completo (ejecute cal 2 para generar calendario en la terminal en linux / unix) observe el día de inicio de la semana del día de cada mes.

  • Cada año normal cambiando un día de la semana y año bisiesto cambiando dos días de la semana.como (365% 7)= 1 y (366% 7)= 2 
 i= y+y/4-y/100+y/400
  • Pero no debemos calcular el día adicional si y es un año bisiesto para el mes 0 y 1 
y-=m<3

  • pero de esta manera también estamos eliminando el día adicional de los años no bisiestos.por lo que llenaremos el vacío restando 1 día por cada mes después de febrero.

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

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top