5.6 Некоторые примеры решения сложных вычислительных задач

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

Задача №1. Необходимо подсчитать количество нулей содержащихся в конце числа, вычисленного по формуле факториала. Например, число 3!=6 имеет ноль нулей, число 5!=120 - один ноль, 10!= 3628800- два нуля.

Понятно, что самым простым решением является написать функцию вычисления факториала, затем полученное число делить его на 10, пока делимое делится нацело, таким образом подсчитать число нулей. Или преобразовать число в строку символов и подсчитать количество символов ’0’ в конце строки.

При небольших значениях аргумента факториала можно воспользоваться стандартной арифметикой, но при увеличении аргумента приходится перейти на собственную арифметику (см. раздел ). Однако для совсем больших чисел, например 10000! или 100000! время вычисления будет слишком велико. Рассмотрим теперь особенности данной конкретной задачи. Если внимательно изучить появление нулей в конце числа, то можно обнаружить, что ноль появляется, если число в произведении кратно 5. Первый ноль появляется в числе 5!=120, второй ноль в числе 10! Нетрудно подсчитать число нулей в числе 100! Их будет 24. Числа дающие в произведении по одному нулю (5, 10, 15, 20, 30, 35, 40, 45, 55, 60, 65, 70, 80, 85, 90, 95), а числа 25, 50, 75, 100 дают по два нуля.

Таким образом, алгоритм подсчета нулей в числе n! следующий:

Шаг 1 I=0, s=0 Шаг 2 I=I+1 Шаг 3 определяем j как степень кратности числа I числу 5. Шаг 4 s=s+j Шаг 5 переходим на шаг 2, пока не достигнем равенства I=n

//функция подсчета степени кратности 5
int CountZero(int num)
{
      int i=0;
      while(1)
      {
            if(num%5==0) {
                  i++;
                  num=num/5;
            }
            else break;
      }
      return i;
}
//подсчет числа нулей в конце числа 10000!
void main()
{
      int count=0;
      for(int i=1; i<=10000; i++)
      {
            int z=CountZero(i);
            count=count+z;
      }
      printf("%d\n",count);
}

Задача №2. Дано число n. Необходимо определить является ли число Фибоначчи F(n) четным.

Решение 1. Вычислить число F(n) и проверить делимость на 2. Однако, учитывая быстрый рост чисел Фибоначчи, такое решение может быть для сравнительно малых чисел.

Решение 2. Если учесть, что четность можно определить по последней десятичной цифре числа, то можно предложить другое решение, которое не требует вычисление всего числа, а только последней десятичной цифры. Алгоритм будет похож на алгоритм вычисления числа Фибоначчи, но только учитывается последняя цифра.

//Функция определения четности числа Фибоначчи(100000);
fibo()
{
      int i1=1;
      int i2=1;
      int fi;
      for(int i=0; i<100000; i++)
      {
            fi=i1+i2; //вычисляем суммы двух предыдущих чисел
            if(fi/10) fi=fi%10;//если сумма больше 10, то берем остаток от деления 10
            i1=i2; //корректируем значения i1 и i2 для вычисления следующего числа
            i2=fi;
      }
      if(fi%2==0) printf("Number fi(100000) is even"); //число четное
      else printf("Number fi(100000) is no even"); //число нечетное
}