Как найти високосный год программно в C - PullRequest
Новая
       11

Как найти високосный год программно в C

7 голосов
/ 10 июля 2010

Я создал программу на C, чтобы определить, является ли введенный год високосным или нет. Но, к сожалению, это не работает хорошо. В нем говорится, что год является високосным, а предыдущий год не является високосным. 

#include<stdio.h>
#include<conio.h>
int yearr(int year);
void main(void)
{
    int year;
    printf("Enter a year:");
    scanf("%d",&year);
    if(!yearr(year))
    {
        printf("It is a leap year.");
    }
    else
    {
    printf("It is not a leap year");
    }


getch();
}
int yearr(int year)
{
    if((year%4==0)&&(year/4!=0))
    return 1;
    else
    return 0;
}

После прочтения комментариев я отредактировал кодировку следующим образом: 

#include<stdio.h>
#include<conio.h>
int yearr(int year);
void main(void)
{
    int year;
    printf("Enter a year:");
    scanf("%d",&year);
    if(!yearr(year))
    {
        printf("It is a leap year.");
    }
    else
    {
    printf("It is not a leap year");
    }


getch();
}
int yearr(int year)
{
    if((year%4==0)
    {
    if(year%400==0)
    return 1;
    if(year%100==0)
    return 0; 
    }
    else
    return 0;
}

Ответы [ 15 ]

110 голосов
/ 22 июля 2012

Самый эффективный тест високосного года: 

if ((year & 3) == 0 && ((year % 25) != 0 || (year & 15) == 0))
{
    /* leap year */
}

Этот код действителен на C, C ++, C #, Java и многих других C-подобных языках. В коде используется одно выражение ИСТИНА / ЛОЖЬ, состоящее из трех отдельных тестов:

  • 4-й год теста: year & 3
  • 100-й год теста: year % 25
  • 400-й год теста: year & 15

Полное обсуждение того, как работает этот код, приведено ниже, но сначала требуется обсуждение алгоритма Википедии:

Алгоритм Википедии НЕ УКАЗАН / НЕ НАДЕЖЕН

Википедия опубликовала алгоритм псевдокода (см .: Википедия: високосный год - алгоритм ), который подвергался постоянному редактированию, мнению и вандализму.

НЕ ИСПОЛЬЗУЙТЕ АЛГОРИТМ ВИКИПЕДИИ!

Один из самых старых (и неэффективных) алгоритмов Википедии выглядит следующим образом: 

if year modulo 400 is 0 then
   is_leap_year
else if year modulo 100 is 0 then
   not_leap_year
else if year modulo 4 is 0 then
   is_leap_year
else
   not_leap_year

Вышеприведенный алгоритм неэффективен, потому что он всегда выполняет тесты для 400-го и 100-го года, даже в те годы, которые быстро не пройдут "тест 4-го года" (тест по модулю 4) - что составляет 75% времени! Переупорядочив алгоритм для выполнения теста 4-го года, мы значительно ускорим процесс.

"НАИБОЛЕЕ ЭФФЕКТИВНЫЙ" АЛГОРИТМ ПСЕВДО-КОДА

Я предоставил Википедии следующий алгоритм (более одного раза): 

if year is not divisible by 4 then not leap year
else if year is not divisible by 100 then leap year
else if year is divisible by 400 then leap year
else not leap year

Этот «наиболее эффективный» псевдокод просто меняет порядок тестов, поэтому сначала выполняется деление на 4, а затем менее часто встречающиеся тесты. Поскольку «год» не делится на четыре 75% времени, алгоритм заканчивается после одного теста в трех из четырех случаев.

ПРИМЕЧАНИЕ: Я боролся с различными редакторами Википедии, чтобы улучшить опубликованный там алгоритм, утверждая, что многие начинающие & mdash; и профессиональные & mdash; программисты быстро приходят на страницу Википедии (благодаря спискам лучших поисковых систем) и реализуют Псевдокод Википедии без каких-либо дополнительных исследований. Редакторы Википедии отвергали и удаляли все попытки, которые я предпринял, чтобы улучшить, комментировать или даже просто сносить опубликованный алгоритм. Очевидно, они считают, что поиск эффективности - это проблема программиста. Это может быть правдой, но многие программисты слишком спешат, чтобы провести тщательное исследование!

ОБСУЖДЕНИЕ "НАИБОЛЕЕ ЭФФЕКТИВНОГО" ЛИСТОВОГО ИСПЫТАНИЯ

Бит-И вместо модуля:

Я заменил две операции по модулю в алгоритме Википедии на операции побитового И. Почему и как?

Выполнение вычисления по модулю требует деления. При программировании ПК не часто задумываться над этим, но при программировании 8-битных микроконтроллеров, встроенных в небольшие устройства, вы можете обнаружить, что функция деления не может быть выполнена процессором по умолчанию. В таких процессорах деление является трудным процессом, включающим в себя повторяющиеся циклы, сдвиг битов и операции сложения / вычитания, которые выполняются очень медленно. Очень желательно избегать.

Оказывается, что по модулю степеней двух можно поочередно достичь с помощью операции побитового И (см .: Википедия: Операция по модулю - Проблемы производительности ):

x% 2 ^ n == x & (2 ^ n - 1)

Многие оптимизирующие компиляторы преобразуют такие операции по модулю в побитовое И для вас, но менее продвинутые компиляторы для меньших и менее популярных процессоров могут этого не делать. Побитовое И - это отдельная инструкция на каждом процессоре.

Заменив тесты modulo 4 и modulo 400 на & 3 и & 15 (см. Ниже: «Факторинг для уменьшения математики»), мы можем гарантировать, что самый быстрый код получится без использования гораздо более медленной операции деления.

Не существует степени двойки, равной 100. Таким образом, мы вынуждены продолжать использовать операцию по модулю для теста 100-го года, однако 100 заменяется на 25 (см. Ниже).

Факторинг для упрощения математики:

Помимо использования побитового И для замены операций по модулю, вы можете заметить два дополнительных спора между алгоритмом Википедии и оптимизированным выражением:

  • modulo 100 заменяется на modulo 25
  • modulo 400 заменяется на & 15

Для теста 100-го года используется modulo 25 вместо modulo 100. Мы можем сделать это, потому что коэффициент 100 равен 2 x 2 x 5 x 5. Поскольку тест 4-го года уже проверяет факторы 4, мы можем исключить этот коэффициент из 100, оставив 25. Эта оптимизация, вероятно, незначительна почти для каждой реализации ЦП ( как 100, так и 25 соответствуют 8 битам).

В тесте 400-го года используется & 15, что эквивалентно modulo 16. Опять же, мы можем сделать это, потому что 400 факторов до 2 x 2 x 2 x 2 x 5 x 5. Мы можем исключить фактор 25, который проверяется тестом 100-го года, оставляя 16. Мы не можем дополнительно уменьшить 16, потому что 8 фактор 200, поэтому устранение любых других факторов приведет к нежелательному положительному результату в течение 200-го года.

Оптимизация 400-го года очень важна для 8-битных процессоров, во-первых, потому что она избегает деления; но, что более важно, потому что значение 400 - это 9-битное число, с которым гораздо сложнее работать в 8-битном процессоре.

Операторы логического И / ИЛИ короткого замыкания:

Последней и наиболее важной используемой оптимизацией являются логические операторы короткого замыкания И ('&&') и ИЛИ ('||') (см .: Википедия: Оценка короткого замыкания ), которые реализованы в большинстве C-подобных языков. Операторы короткого замыкания названы так, потому что они не удосуживаются оценить выражение на правой стороне, если выражение на левой стороне, само по себе, определяет результат операции.

Например: если 2003 год, то year & 3 == 0 ложно. Невозможно, чтобы тесты в правой части логического И могли сделать результат верным, поэтому больше ничего не оценивается.

При первом выполнении теста 4-го года, только тест 4-го года (простое побитовое И) оценивается в три четверти (75 процентов) времени. Это значительно ускоряет выполнение программы, тем более что оно позволяет избежать деления, необходимого для теста на 100-й год (операция по модулю 25).

ПРИМЕЧАНИЕ ПО РАЗМЕЩЕНИЮ РОДИТЕЛЕЙ

Один комментатор счел, что в моем коде неуместны скобки, и предложил перегруппировать подвыражения вокруг логического оператора AND (а не вокруг логического ИЛИ) следующим образом: 

if (((year & 3) == 0 && (year % 25) != 0) || (year & 15) == 0) { /* LY */ }

Выше указано неверное. Логический оператор И имеет более высокий приоритет, чем логический ИЛИ, и будет оцениваться первым с новыми скобками или без них. Скобки вокруг логических аргументов AND не влияют. Это может привести к полному исключению подгрупп: 

if ((year & 3) == 0 && (year % 25) != 0 || (year & 15) == 0) { /* LY */ }

Но в в обоих случаях, приведенных выше, правая часть логического ИЛИ (критерий 400-го года) оценивается почти каждый раз (т. Е. Годы не делятся на 4 и 100). ). Таким образом, полезная оптимизация была ошибочно исключена.

Скобки в моем исходном коде реализуют наиболее оптимизированное решение: 

if ((year & 3) == 0 && ((year % 25) != 0 || (year & 15) == 0)) { /* LY */ }

Здесь логическое ИЛИ оценивается только для лет, кратных 4 (из-за короткого замыкания И). Правая часть логического ИЛИ оценивается только на годы, кратные 4 и 100 (из-за короткого замыкания ИЛИ).

ПРИМЕЧАНИЕ ДЛЯ ПРОГРАММИСТОВ C / C ++

Программисты на C / C ++ могут подумать, что это выражение более оптимизировано: 

if (!(year & 3) && ((year % 25) || !(year & 15))) { /* LY */ }

Это не более оптимизировано! Хотя явные тесты == 0 и != 0 удалены, они становятся неявными и все еще выполняются. Хуже того, код больше не действует в строго типизированных языках, таких как C #, где year & 3 оценивается как int, но логические операторы AND (&&), OR (||) и NOT (!) требуют bool аргументов.

13 голосов
/ 10 июля 2010

Ваша логика определения високосного года неверна.Это должно начать вас (из Википедии): 

if year modulo 400 is 0
       then is_leap_year
else if year modulo 100 is 0
       then not_leap_year
else if year modulo 4 is 0
       then is_leap_year
else
       not_leap_year

x modulo y означает остаток от x, деленный на yНапример, 12 по модулю 5 равно 2.

6 голосов
/ 10 июля 2010 
int isLeapYear(int year)
{
   return (year % 400 == 0) || ( ( year % 100 != 0) && (year % 4 == 0 ));
}
4 голосов
/ 21 мая 2015

Это может быть правильным решением. Алгоритм, указанный в Википедии, неверен. 

-(BOOL)isLeapYear: (int)year{    

    if(year%4==0){
      if(year%100!=0){
        return YES;
     }
     else if(year%400!=0){
        return YES;
     }
     else return NO;
   }

    else return NO;
  }
4 голосов
/ 29 сентября 2011

Хотя логика, которая сначала делит на 400, безупречна, она не так эффективна в вычислительном отношении, как сначала деление на 4. Вы можете сделать это с помощью логики: 

#define LEAPYEAR(y) (((y) % 4) == 0 && (((y) % 100) != 0 || ((y) % 400) == 0))

Это делит на 4 для каждого значения, но для 3/4 из них тестирование заканчивается там. Для 1/4, прошедшей первый тест, она делится на 100, исключая значения 24/25; для оставшихся 1 из 100 он тоже делится на 400 и дает окончательный ответ. Конечно, это не огромная экономия.

3 голосов
/ 10 июля 2010

С Статья в Википедии о Високосный год : 

if (year modulo 4 is 0) and (year modulo 100 is not 0) or (year modulo 400 is 0)
   then is_leap_year
else
   not_leap_year
2 голосов
/ 10 июля 2010

Проблема с вашим кодом заключается в том, что вы возвращаете ненулевое значение из yearr, если считаете, что год является високосным.Так что вам не нужно ! в вашем операторе if.

1 голос
/ 26 июля 2017 
I used this code:

#include <stdio.h>

int main()
{
    int yr;
    printf ("Enter a year \n");
    scanf ("%d", &yr);

    if (yr%400 == 0)
        printf("\n LEAP YEAR.");

    else if (yr%4==0 && yr%100!=0)
        printf("\n LEAP YEAR.");
    else
        printf ("\n NOT LEAP YEAR.");
}
1 голос
/ 26 ноября 2014 

    #include 
    void main(void)
    {
        int year;
        printf("Enter a year to check if it is Leap Year\n");
        scanf("%d",&year);
        if(year%400==0) /*<a href="http://programmingansic.blogspot.com/2014/11/the-reason-for-leap-year.html" rel="nofollow"> Why  mod 400</a> */
            printf("%d is a Leap Year\n",year);
        else if(year%100==0) /*<a href="http://programmingansic.blogspot.com/2014/11/the-reason-for-leap-year.html" rel="nofollow">  Why  mod 100</a>  */
            printf("%d is not a Leap Year\n",year);
        else if(year%4==0)
            printf("%d is a Leap Year\n",year);
        else
            printf("%d is not a Leap Year\n",year);

    }
1 голос
/ 10 июля 2010 
 if(year%400 ==0 || (year%100 != 0 && year%4 == 0))
    {
        printf("Year %d is a leap year",year);
    }
    else
    {
        printf("Year %d is not a leap year",year);
    }

Измените это, как указано выше. Также прочитайте это .

Страница:
...