数论模运算如何计算调整
Number theory modular arithmetic how to account for adjustments
我不确定我的解决方案是否合理 (ans. 171) - Project Euler Q.19 因为我很难理解模块化算法并且不确定我的方法是否正确或不是...我在尝试获得将 0 作为键而不是 1 到星期一以在散列 table 中引用的等价性时遇到了麻烦。问题是;
- 1 Jan 1900 was a Monday.
- Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, which has twenty-eight, rain
or shine. And on leap years, twenty-nine.
- A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth
century (1 Jan 1901 to 31 Dec 2000)?
所以我所做的是从 1 开始计算天数总和(参考散列 table 中的天数)并在找到星期天的总和后减去 1,因为按 0 计算总和会导致问题天数可被 3 和 6 整除(3:星期三,6:Sunday)。我怎么能通过使用 0 作为星期一的参考来做到这一点?
import java.util.*;
public class p19 {
public static void main(String[] args) {
Hashtable<Integer, String> days = new Hashtable<Integer, String>();
days.put(1, "Monday");
days.put(2, "Tuesday");
days.put(3, "Wednesday");
days.put(4, "Thursday");
days.put(5, "Friday");
days.put(6, "Saturday");
days.put(7, "Sunday");
Hashtable<Integer, String> months = new Hashtable<Integer, String>();
months.put(1, "January");
months.put(2, "February");
months.put(3, "March");
months.put(4, "April");
months.put(5, "May");
months.put(6, "June");
months.put(7, "July");
months.put(8, "August");
months.put(9, "September");
months.put(10, "October");
months.put(11, "November");
months.put(12, "December");
int min, max;
min = 1900;
max = 2000;
String[][] arr = new String[12 * (max - min + 1)][];
// Total days starts at 1 to make modular arithmetic easier when accounting for days
// (i.e., 1 Monday, 2 Tuesday, etc.) and since the first day, hence, 0th day on 1 Jan 1900 is Monday.
for (int year = min, index = 0, totalDays = 1; year <= max; year++) {
for (int month = 1; month <= 12; month++, index++) {
arr[index] = new String[numberOfDays(month,year)];
int sum = 1;
System.out.println(months.get(new Integer(month)) + " " + year);
for (int day = 1; day <= numberOfDays(month, year); day++, totalDays++) {
if (totalDays % 7 == 0) {
arr[index][day - 1] = days.get(new Integer((totalDays % 7 + 7) % 365));
}
else {
arr[index][day - 1] = days.get(new Integer((totalDays % 7) % 365));
}
if (sum > 7) {
System.out.println();
sum = 1;
}
System.out.print(totalDays + ":= " + arr[index][day - 1] + ", " + day + " | ");
sum++;
}
System.out.println("\n");
}
}
int count = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i][0] == "Sunday") {
count++;
}
}
// Subtract 1 from count since the total days were overstated by 1 before inititallizing array
System.out.println("Number of Sundays that fell on the first of the month from: 1/Jan/1901 - 31/Dec/2000: " + (count - 1));
}
public static int numberOfDays (int month, int year) {
int days = 0;
switch (month) {
case 7:
case 4:
case 6:
case 11:
days = 30;
break;
case 2:
if (isLeapYear(year)) {
days = 29;
}
else {
days = 28;
}
break;
default: days = 31;
break;
}
return days;
}
public static boolean isLeapYear(int year) {
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
}
您的 daysInMonth 检查不正确 - 结果一定是正确的:
switch (month) {
case 4:
case 6:
case 9:
case 11:
days = 30;
break;
程序的其余部分可以简化 - 请注意,起始年份也必须更正,dow 代表 DayOfWeek:
public static void main (String[] args) {
int count = 0;
// dow = 2, since 1.1.1901 was a Thuesday (2)
for (int year = 1901, dow = 2; year <= 2000; ++year)
{
for (int month = 1; month <= 12; ++month)
{
if (dow == 0) {
// System.out.println ("Date: " + year + "-" + month);
++count;
}
dow = (dow + numberOfDays (month, year)) % 7;
}
}
System.out.println ("Number of Sundays that fell on the first of the month from: 1/Jan/1901 - 31/Dec/2000: " + count);
}
我不确定我的解决方案是否合理 (ans. 171) - Project Euler Q.19 因为我很难理解模块化算法并且不确定我的方法是否正确或不是...我在尝试获得将 0 作为键而不是 1 到星期一以在散列 table 中引用的等价性时遇到了麻烦。问题是;
- 1 Jan 1900 was a Monday.
- Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, which has twenty-eight, rain
or shine. And on leap years, twenty-nine.- A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
所以我所做的是从 1 开始计算天数总和(参考散列 table 中的天数)并在找到星期天的总和后减去 1,因为按 0 计算总和会导致问题天数可被 3 和 6 整除(3:星期三,6:Sunday)。我怎么能通过使用 0 作为星期一的参考来做到这一点?
import java.util.*;
public class p19 {
public static void main(String[] args) {
Hashtable<Integer, String> days = new Hashtable<Integer, String>();
days.put(1, "Monday");
days.put(2, "Tuesday");
days.put(3, "Wednesday");
days.put(4, "Thursday");
days.put(5, "Friday");
days.put(6, "Saturday");
days.put(7, "Sunday");
Hashtable<Integer, String> months = new Hashtable<Integer, String>();
months.put(1, "January");
months.put(2, "February");
months.put(3, "March");
months.put(4, "April");
months.put(5, "May");
months.put(6, "June");
months.put(7, "July");
months.put(8, "August");
months.put(9, "September");
months.put(10, "October");
months.put(11, "November");
months.put(12, "December");
int min, max;
min = 1900;
max = 2000;
String[][] arr = new String[12 * (max - min + 1)][];
// Total days starts at 1 to make modular arithmetic easier when accounting for days
// (i.e., 1 Monday, 2 Tuesday, etc.) and since the first day, hence, 0th day on 1 Jan 1900 is Monday.
for (int year = min, index = 0, totalDays = 1; year <= max; year++) {
for (int month = 1; month <= 12; month++, index++) {
arr[index] = new String[numberOfDays(month,year)];
int sum = 1;
System.out.println(months.get(new Integer(month)) + " " + year);
for (int day = 1; day <= numberOfDays(month, year); day++, totalDays++) {
if (totalDays % 7 == 0) {
arr[index][day - 1] = days.get(new Integer((totalDays % 7 + 7) % 365));
}
else {
arr[index][day - 1] = days.get(new Integer((totalDays % 7) % 365));
}
if (sum > 7) {
System.out.println();
sum = 1;
}
System.out.print(totalDays + ":= " + arr[index][day - 1] + ", " + day + " | ");
sum++;
}
System.out.println("\n");
}
}
int count = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i][0] == "Sunday") {
count++;
}
}
// Subtract 1 from count since the total days were overstated by 1 before inititallizing array
System.out.println("Number of Sundays that fell on the first of the month from: 1/Jan/1901 - 31/Dec/2000: " + (count - 1));
}
public static int numberOfDays (int month, int year) {
int days = 0;
switch (month) {
case 7:
case 4:
case 6:
case 11:
days = 30;
break;
case 2:
if (isLeapYear(year)) {
days = 29;
}
else {
days = 28;
}
break;
default: days = 31;
break;
}
return days;
}
public static boolean isLeapYear(int year) {
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
}
您的 daysInMonth 检查不正确 - 结果一定是正确的:
switch (month) {
case 4:
case 6:
case 9:
case 11:
days = 30;
break;
程序的其余部分可以简化 - 请注意,起始年份也必须更正,dow 代表 DayOfWeek:
public static void main (String[] args) {
int count = 0;
// dow = 2, since 1.1.1901 was a Thuesday (2)
for (int year = 1901, dow = 2; year <= 2000; ++year)
{
for (int month = 1; month <= 12; ++month)
{
if (dow == 0) {
// System.out.println ("Date: " + year + "-" + month);
++count;
}
dow = (dow + numberOfDays (month, year)) % 7;
}
}
System.out.println ("Number of Sundays that fell on the first of the month from: 1/Jan/1901 - 31/Dec/2000: " + count);
}