Модульная арифметика теории чисел, как учитывать корректировки

Я не уверен, что мое решение оправдано (ответ 171) - Project Euler Q.19, так как мне трудно понять модульную арифметику, и я не совсем уверен, был ли мой подход к ней правильным или нет... я возникли проблемы при попытке получить эквивалентность наличия 0 в качестве ключа, а не 1 для понедельника для ссылки в хеш-таблице. Вопрос был;

  • 1 января 1900 года был понедельник.
  • Тридцать дней приходится на сентябрь, апрель, июнь и ноябрь. У всех остальных тридцать один, За исключением одного Февраля, у которого двадцать восемь, будь то дождь
    . А в високосные годы двадцать девять.
  • Високосный год наступает в любой год, который без остатка делится на 4, но не в век, если он не делится на 400.

Сколько воскресений приходилось на первое число месяца в двадцатом веке (с 1 января 1901 г. по 31 декабря 2000 г.)?

Итак, что я сделал, так это начал сумму дней с 1 (ссылка на дни в хеш-таблице) и вычел 1 после нахождения суммы воскресенья, поскольку выполнение этого с 0 вызывало проблемы, когда общая сумма дней делилась на 3 и 6 ( 3:среда, 6:воскресенье). Как я мог сделать это, используя 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);
    }
} 

person Patrick Olila    schedule 11.04.2018    source источник
comment
Должен признаться, я не понимаю вашего подхода. ИМХО, вы либо берете первое воскресенье 1901 года и добавляете +7 к каждой дате, затем проверяете, является ли дата ГГГГ-ММ-01. Или вы берете годы с 1901 по 2000 год, месяцы с 1 по 12, генерируете дату y/m/01 и проверяете, воскресенье ли это. Итак, вы пытались решить эту проблему без date/time-lib. Но зачем вам названия месяцев? А для чего называются дни недели? И без использования библиотеки даты/времени, зачем индексировать дни и месяцы, начиная с 1, что трудно сделать правильно с операциями по модулю?   -  person user unknown    schedule 11.04.2018
comment
Кстати. вот подход оболочки, но с использованием функции даты: for x in {0..36525..7}; do date -d "6 Jan 1901 +$x days" | grep "So 1\." ; done | wc -l 171 и здесь другой подход (так же как и воскресенье в моей локали) cnt=0; for y in {1901..2000}; do for m in {1..12}; do dow=$(date -d "$y-$m-01" +%a); if [[ $dow == "So" ]] ; then ((++cnt)); fi; done; done; echo $cnt Результат: 171   -  person user unknown    schedule 11.04.2018
comment
До сих пор я не знал о дате/времени-библиотеке, спасибо. И мне было трудно визуализировать, поэтому я сделал массив для печати LOL.   -  person Patrick Olila    schedule 11.04.2018
comment
Ну, как упражнение для операции по модулю, это не было потрачено впустую. И библиотека java datetime (java.util.Date) представила интерфейс, в котором getMonth возвращает 0 для января, что прекрасно работает с другими функциями, но, конечно, все ожидают, что 6 будет относиться к июню. Я предполагаю, что более новые замены избежали этой ловушки, в которую попал почти каждый новичок, и даже опытные программисты иногда попадали в нее. :)   -  person user unknown    schedule 11.04.2018
comment
Большое спасибо, очень ценю это!   -  person Patrick Olila    schedule 12.04.2018


Ответы (1)


Ваша проверка 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);
}
person user unknown    schedule 11.04.2018
comment
Утверждение о ложной ошибке было неверным. Имел (count-1) в операторе println :). - person user unknown; 11.04.2018