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

7 minutos de lectura

avatar de usuario
Harikrishnan

Estoy usando el algoritmo de Sakamoto para averiguar el día de la semana a partir de una fecha determinada. ¿Alguien puede decirme la corrección de este algoritmo? Solo 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;
}

avatar de usuario
Nemo

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

los 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 extra (si lo hay) en el final del año; o mejor dicho, al final del anterior año. Entonces, 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 agregado 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 es 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 y término está contribuyendo; añade uno al día por 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, solo podemos agregar y/4 a la suma para contar cuantos dias bisiestos pasan en y años. (Tenga en cuenta que esta fórmula asume rondas de división de enteros abajo.)

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

Excepto que cada 400 años es un año bisiesto nuevamente. 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 del mes dentro del año son bastante arbitrarios).

Luego, tome todo el mod 7, ya que esa es la duración de una semana.

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

Por cierto, la declaración de Wikipedia de que el calendario es “bueno hasta 9999” es totalmente arbitraria. Esta fórmula es buena por el tiempo que permanezcamos con el Calendario Gregorianoya sea 10 años, 100 años, 1000 años o 1 millón de años.

[edit]

El argumento anterior es esencialmente una prueba por inducción. Es decir, asumiendo que la fórmula funciona para un determinado (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, ¿cambia la suma en la cantidad correcta a medida que pasa de un año al siguiente? Con el conocimiento de las reglas del año bisiesto, y con el “año virtual” que tiene el día adicional al final del año, lo hace trivialmente.

  • ¿Puede explicar la matriz t? No soy capaz de resolverlo.

    – Nivetha

    08/02/2014 a las 18:35

  • @ user1677597 Para obtener información sobre t array, visite: quora.com/How-does-Tomohiko-Sakamotos-Algorithm-work

    – Mitesh Pathak

    14 de septiembre de 2014 a las 9:17

  • Vale la pena señalar que el calendario gregoriano (también conocido como occidental) COMIENZA el 1 de marzo. Si desea leer más sobre esto, lea el excelente The Long Painful History of Time de Naggum: naggum.no/lugm-time.html

    – Haakon Løtveit

    17 de julio de 2017 a las 16:01

  • Solo quiero agregar esto: c++ int t[] = {11,12,1,2,3,4,5,6,7,8,9,10}; Tenga en cuenta la fórmula: (2,6 * m – 0,2) mod 7, por supuesto, esto es (int). esto da esa matriz: 0 3 2 5 0 3 5 1 4 6 2 4

    – Krupesh Anadkat

    8 de septiembre de 2019 a las 4:07


  • No entendí la parte donde estamos restando 1 de todos los meses excepto enero y febrero. ¿Podría alguien explicar por favor?

    – Sumit

    20 de abril de 2020 a las 5:15

avatar de usuario
csharpfolk

Recientemente escribí una publicación de blog sobre este algoritmo aquí.

La idea básica detrás del algoritmo es que febrero y enero cuenten los días de la semana desde el 31 de diciembre del año anterior. Para todos los demás meses, contaremos el día de la semana desde Actual año 31 de diciembre Hacemos esto en dos pasos primero calculamos el día de la semana del último día del mes anterior al mes actual m entonces solo agregamos d módulo siete.

El 31 de diciembre del 1 a. C. es el domingo que está codificado como 0, el lunes es 1, etc. Así que tenemos: 0 + y + y/4 - y/100 + y/400 esto con y -= m < 3 calcula el día de la semana del 31 de diciembre del año en curso o del año anterior (según el mes). Nota: 365 % 7 == 1 esto explica por qué escribimos y en lugar de 365*y. El último componente d es obvio ya que comenzamos a contar el día de la semana desde el último día del mes anterior.

La última parte que debe explicarse son los valores en la matriz, para los primeros dos valores, estos son la cantidad de días desde el año pasado, el 31 de diciembre, hasta el comienzo del mes. % 7. Para el resto de los meses son módulo siete negado número de días desde el final del mes anterior hasta el 31 de diciembre del año en curso. En otras palabras, estamos restando días por suma módulo 7, por ejemplo (a-b)%7 = (a+(7-b%7))%7.

Puede encontrar más explicaciones en la publicación de mi blog.

avatar de usuario
krupesh anadkat

Esta podría no ser una respuesta completa como algunas 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 los meses que comienzan en marzo y terminan en febrero, como dijeron otros:

  1. marzo
  2. abril
  3. Mayo
  4. junio
  5. mes de julio
  6. agosto
  7. septiembre
  8. octubre
  9. noviembre
  10. diciembre
  11. enero
  12. febrero

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

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

Ahora, para todos los elementos en la matriz, simplemente haga: (2.6*m - 0.2) mod 7
analiza el resultado como entero y obtendrás esto:
0 3 2 5 0 3 5 1 4 6 2 4

  • Puedes encontrar esta fórmula aquí: wikipedia
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;
}

esta : + 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 -> cierto
  2. SI perfectamente divisible por 100 pero no por 400 -> Falso
  3. Divisible por 4 -> Cierto

realice comprobaciones en el orden anterior. Tal vez por eso restaron y/100 y sumaron y/4 & y/400. Sí lógica tonta 😅

Sé que esta podría no ser la respuesta, Pero esto podría ayudar a aquellos a quienes les resulta difícil recordar/comprender cosas., ¡Si! no todos tenemos altos niveles de coeficiente intelectual para comprender cosas y, lamentablemente, algunos de nosotros tampoco podemos recordar cosas, jajaja.

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:

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

y compararlo con un calendario de un año completo (ejecutar cal 2para generar el 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 cambia un día de la semana y año bisiesto cambia 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 extra 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. así que llenaremos el espacio 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};

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad