Codechef: ошибка неправильного ответа в smallfactorial

#include<stdio.h>
int fact(int k)
{
int j,f=1;
for(j=1;j<=k;j++)
f*=j;
return f;
}
int main()
{
int t,i,n[100],s[100],j;
scanf("%d",&t);
for(i=0;i</stdio.h>
<p> Вас попросят рассчитать факториалы некоторых небольших натуральных чисел. вход</p> <p> Целое число t, 1 <= t <=100, обозначающее количество тестовых мест, за которыми следуют t строк, каждая из которых содержит одно целое число n, 1 <=n <=100. Вывод</p> <p> Для каждого целого числа n, заданного на входе, отобразите строку со значением n! пример</p> <p> Пример ввода: 4 1 2 5 3 Выход образца: 1 2 120 6</p>
3 ответа

Ваш код даст правильные результаты для данных тестов, но это не доказывает, что ваш код работает. Это неверно из-за переполнения целых чисел. Попробуйте вычислить 100! по вашей программе, и вы увидите, в чем проблема.

В моем ответе не было деталей. Я обновлю это, чтобы добавить детали для ответа на вопрос, поскольку он стоит сейчас.

C имеет ограничения по максимальному и минимальному размерам, которые могут быть сохранены в переменной. Для произвольной арифметики точности обычно рекомендуется использовать библиотеку bignum, предложенную PHIFUND.

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

Первоначально использование таких больших массивов может быть уменьшено. Вместо использования массива из 100 переменных для хранения тестовых примеров может использоваться одна переменная. Использование большого массива и чтения в тестовых случаях может дать оптимизацию, только если вы используете буфера для чтения в из stdin, иначе она не будет лучше, чем вызов scanf для чтения тестовых случаев, добавив scanf в for цикла для перехода по отдельным тестовым случаям.

Это ваш выбор либо использовать буферизацию для повышения скорости, либо для создания целого числа вместо массива из 100 целых чисел. В обоих случаях будут улучшения по сравнению с текущим решением, связанным с кодеком по OP. Для буферизации вы можете обратиться к этому вопросу. Если вы видите результаты синхронизации на кодексе, результат буферизации может быть невидим, поскольку количество операций в остальной части логики велико.

Теперь второй вопрос об использовании array[200]. В блоге, посвященном кодеку, используется массив из 200 элементов для демонстрации логики. Это наивный подход, как указывает сам учебник. Хранение одной цифры в каждом месте массива - огромная потеря памяти. Этот подход также приводит к значительно большему количеству операций, приводящих к более медленному решению. Целое число может хранить как минимум 5 цифр (-32768 до 32767) и обычно может хранить больше. Вы можете сохранить промежуточные результаты в long long int используемом как ваш temp и использовать все 5 цифр. Это упрощение привело бы к использованию только arr[40] вместо arr[200]. Коду потребуются некоторые дополнительные изменения, чтобы позаботиться о переносе вперед, и станет немного более сложным, но как скорость, так и улучшение памяти будут видны.

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

Я предлагаю вам поставить свой код на codereview для проверки вашего кода. Есть еще много вопросов, которые лучше всего пересмотреть там.


выше программа работает только для небольших чисел, что означает до 7 !, после чего этот код не дает правильных результатов, потому что 8! значение - 40320. В языке c Диапазон SIGNED INTEGER - -32768 - +32767, но факториальные значения> 8 находятся за пределами этого значения, поэтому целочисленные могут хранить эти значения, поэтому выше кода не может дать правильные результаты для получения правильных значений, которые мы объявляем s [100] как LONG INT, но он также работает только для некоторого диапазона


Здесь ваш индекс массива должен начинаться с 0 не 1, я имею в виду, что j и i должны быть инициализированы для цикла 0 in for.

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

И если моя догадка правильная, вы используете turbo C, если да, то моя рекомендация заключается в том, что вы начинаете использовать MinGW или Cygwin и пытаетесь скомпилировать CLI, во всяком случае, просто рекомендацию.

Может быть, может возникнуть еще одна проблема: почему codechef не принимает ваш код, который вы определили, чтобы принять целое число, а затем вы передаете массив, может быть, этот код будет работать для вас:

#include<stdio.h>
int fact(int a[],int n)// here in function prototype I have defined it to take array as argument where n is array size.
{
 int j=0,f=1,k;
 for (k=a[j];k>0;k--)
 f*=k;
 return f;
}
int main()
{
 int t,i,n[100],s[100],j;
 setbuf(stdout,NULL);
 printf("enter the test cases\n");
 scanf("%d",&t); //given t test cases
 for(i=0;i</stdio.h>
<p> ПРИМЕЧАНИЕ. - <span>После последнего редактирования OP эта реализация имеет некоторые ограничения, она не может рассчитать факториалы для больших чисел, скажем, для <code>100, снова редактирование поставило вопрос на другой трек, и этот ответ подходит только для небольших факториалов

licensed under cc by-sa 3.0 with attribution.