Coincidence
Kim. Larman
Kim has a doctoral degree in computer discipline. He has a strong interest in the database, algorithm and data structure. His contact address is (original text is Danish - Translator Note) 31, DK-5270, Odense N, Denmark, or E-mail to: kslarsen@imada.ou.dk.
Introduction
Bruce Schnell
"Four, six, nine, eleven, 30 days is Qi ..." The children's songs are so singing; maybe you have also turned to cover the place, let the fingers catch the songs only 30 days short month? Such a mouth is very useful to us (I just got this silly children's song), but the computer did not have this "inspiration". Of course, we can write computing programs with a large pile of IF-THEN-Elses statements or several cases, allowing it to calculate a specified date is a day.
However, I prefer Kimlason to bring our new techniques to us in the "Algorithm Trail" this month, because of his way, from a new direction to settle the date calculation. In fact, there is no mathematical formula to calculate a specified date is the day of the week, but we can try it together. If our trial is successful, you can have an easy programming mathematical formula, and use it automatically calculate? The day is a few days.
By the way, if you have designed a more clever algorithm, or if you have a new breakthrough in an existing method, you may want to tell me, I must have a certain understanding. My contact method is Schneier@chinet.com, or leave me a note in the DJJ Editorial Department.
How do you know how to make your computer know how today is Wednesday? Even if your computer is turned off, you set a new date after you restart, and it can immediately know that this day is the day.
When you are still a child, you may have seen a record that records the year, month, day, just add a few numbers, and another table connected to it will tell you that this date is the day. Of course, such a calculation table can also be added in the operating system of the computer hard disk. However, there is a simple way to easily calculate a day is a day; and this method only takes a few memory space, and those forms that can only calculate hundreds of years can be too placed.
If your computer does not have a function of estimate and date corresponding to the date, now you may wish to try the following formula in your own program.
Create formula
First, we must use variables d, m and y to represent the date. For example, in March 1, 1994, use "D = 1, M = 3, Y = 4". Our goal is to let the calculation between 0 and 6. 0 represents Monday, 1 represents Tuesday, 2 represents Wednesday, and so on.
On March 1, 1994 is a Tuesday, "D Mod 7 (Date Variable is divided by 7)))" This formula is effective for the entire March. For example, March 18 is Friday, 18 MOD 7 = 4; and 4 is on Friday. Don't forget, the division of the integer has a close relationship. For example, 26 divided by more than 3 5. This is said that 26 is divided by 7 commercials equal to 3, while 26 divide 7 model (abbreviated as 26 mod 7) equal to 5. The above means 19 mod 7 = 12 mod 7 = 5 mod 7 = 5. In the calculation rules, the negative number is similar to the mode, so it is pushed, and -2 mod 7 = 5, -9 mod 7 = 5.
In a more formal expression, unified use of any integer n and k, then this process can be expressed as n = Qk R, and the value range of Q and R here is equally integrated and 0. Table 1 lists all months of transformation data (Shift Information is translated into "gear data", and further proofreading - translator's note). In order to get regularity as much as possible, February is ranked in the end, the same is true, January is also the case. The formula in Example 1 (a) is created by the mode described in the transformation data column in Table 1. The division in this formula will be a discussion. So the number of applications is the integer closest to the true quotient. Table 2 has drawn interesting values from this feature. With straight, we are not difficult to find that when the value of M (the variable of the month) is incremented by 1 unit, 2M is doubled, while 3 (m 1) / 5 will grow in 3/5.
This is exactly what we imitate 3, 2, 3, 2, and 3 repetitive formats (the bending numbers on the right side of the table show this). Please note that we are in size in addition to the division, then the resulting result from 6 to 2 will increase 3 (the order is 6, 0, 1, 2).
Now, we have found that the correcting method for the monthly decision, and hopes to join it in the act of the MOD7 formula. Take March 1, 1994 as an example, this date M = 3. Note that in Example 1 (b), 8 MOD 7 = 1, so when the entire formula is merged, 1 must be subtracted. When performing operations with 7 for the division mode, it is the same as 6, because -1 mod 7 = 6 mod 7 = 6.
In this way, the formula in Example 1 (c) can calculate the remaining month in this year. In fact, since we put in Table 1 in Table 1, then we can then calculate the first two months of 1995 in 1995 in the last two months of January 1 and 14. This is because, although they are not a complete 3, 2, 3, 2, 3 structure, but it can be the beginning of this structure. In order to make this formula more perfect, we still think that January and February It is the last year of the last year of the last year.
Join the year
Looking down the year, we observed March 1, 1995 and Wednesday. This shows that each year, the calculation results of our formula will increase by 1. This is too simple, we just put the year to add the year. Remind you once, we must ensure that the starting point is correct. Due to 1994 MOD 7 = 6, we must subtract 6 when we add Y to an existing formula. This improved example 2 (a) is more complete.
In 1996, it was a leap year, which brought our next question. On March 1, March 1, Friday, not the Thursday, which is justified. So whenever we meet the leap year plus 1. Judging the rules of the leap year are to be 4, and the year can be tied to 100 and 400 is the leap year. In this way, we add Y / 4 - Y / 100 Y / 400 on the original basis. Again, we must ensure correct from the beginning. Since (1994 / 4--1994 / 100 1994/400) MOD 7 = (498--19 4) MOD 7 = 483 MOD 7 = 0, so no need to do any adjustments. In this way, Example 2 (b) is our ultimate results. This formula can work, unless the current calendar system is changed. As an example, let us try to calculate July 4, 2000: (4 2 * 3 (7 1) / 5 2000 2000/400) MOD 7 = ( 4 14 2000 500--20 5) MOD 7 = 2507 mod 7 = 1, so that day is Tuesday. This formula can also calculate the past date; however, the scope is limited, let us look at September 14, 1752 this Thursday, our formula can only be found here. However, like "Where are you on November 22, 1963, it is easy to deal with the date: (22 2 * 11 3 (11 1) / 5 1963 1963 / 4- -1963 / 100 1963/400) MOD 7 = (22 22 7 1963 490--19 4) MOD 7 = 2489 MOD 7 = 4. That day is Friday.
Example 3 Example 3 is a C language program that automatically calculates the given date in accordance with this formula.
Table 1: Monthly transformation data
Month day change
March 31 3
April 30 2
May 31 3
June 30 2
July 31 3
August 31 3
September 30 2
October 31 3
November 30 2
December 31 3
January 31 3
February 28 3
Table 2: Imitation of the function of transforming data. The formula established in Example 1 can be applied to 1994. Example 2 Extended the function of this formula to an application that can be applied in different years.
Example 3: Expressing the above formula with C language program
/ * The specified date is the day of the week. By default input * /
/ * Digital represents the correct date * /
/ * Establish a given date is the day of the week, assuming input is the correct data * /
#include
Char * name [] = {"Monday",
"Tuesday",
"Wednesday",
"Thursday",
"FrIDay",
"SATURDAY",
"Sunday"
}
Void main () {
INT D, M, Y, A;
Printf ("day:"); fflush (stdout);
Scanf ("% D", & D);
Printf ("Month:"); fflush (stdout); scanf ("% d", & m);
Printf ("Year:"); fflush (stdout);
Scanf ("% d", & y);
/ * January and February Are Treated As Month 13 and 14, * /
/ * respectively, from the year before. * /
IF ((m == 1) || (m == 2)) {
M = 12;
Y--
}
A = (D 2 * m 3 * (M 1) / 5 Y Y / 4 - Y / 100 Y / 400)% 7;
Printf ("IT's a% s. / n", name [a]);
}
/ * January and February were treated as the previous year * /
/ * 13 months and 14 months respectively handled * /
