Первая статья: Факториал, НОД, НОК

Запись от Dani размещена 12.02.2012 в 12:47

Показов 63050 Комментарии 13

Часто приходится наблюдать вопросы\просьбы насчет довольно тривиальные функции. Т.к. это старая тема, я решил все, что придумаю собрать сюда. При нахождении ошибок и предложений, прошу сообщать в ЛС. И так, поехали:
Задача: вычислить n!.
Решение: Факториал(n) – это произведение всех натуральных чисел от 1 до n. Причем, 0!=1. Ну, собственно, решение при помощи рекурсии:
C++

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 #include <iostream>
 
 
long Factorial (int n)
{
    if (n==0 || n==1) 
               return 1;
    else 
               return Factorial(n-1)*n;
}
 
int main()
{
    int n;
    std:: cin >> n;
    std:: cout << Factorial(n) << "\n";
    system ("pause");
    return 0;
}

Pascal

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 var n,i: longint;
 
function Factorial (n: longint): longint;
begin
   if n=0 then 
         Factorial:= 1
    else
         Factorial:= Factorial(n-1)*n;
end;
 
begin
read (n);
 
writeln (Factorial(n));
end.

Существуют решения при помощи циклов:
C++ (цикл For):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 #include <iostream>
 
long Factorial (int n)
{
    long res=1;
    for (int i=1; i<=n; ++i) 
                res*=i;
 
    return res;
}
 
 
int main()
{
    int n;
    std:: cin >> n;
    std:: cout << Factorial(n) << "\n";
    system ("pause");
    return 0;
}

Pascal(цикл For):

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 var n: longint;
 
function Factorial (n: longint): longint;
var res,i: longint;
begin
res:= 1;
 
for i:= 1 to n do 
     res:= res*i;
 
Factorial:= res;
end;
 
begin
read (n);
writeln (Factorial(n));
end.

Однако, значение факториала возрастает очень быстро, поэтому иногда необходимо использовать такие типы, как int64 в Pascal и _int64 в C++.

Но бывают случаи, когда необходимо вычислить, например 1000!. В этом случае, прибегают к использованию длинной арифметики. «Длинная арифметика — в вычислительной технике операции над числами, разрядность которых превышает длину машинного слова данной вычислительной машины», - говорит нам Википедия.

Задача: вычислить НОД (a,b).
Решение: НОД – наибольший общий делитель двух целых чисел. Например, НОД (12, 15) = 3. НОД двух взаимно-простых чисел равен 1.
В свое время я мучился с НОД (0,0), по этому подому Википедия сообщает: «Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.».

В разделе «C++ для начинающих», существует тема, посвященная НОДу - https://www.cyberforum.ru/cpp-... 65854.html .

Реализация через остатки на Pascal

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 var a,b: longint;
 
function Nod (a,b: longint): longint;
begin
 
while (a<>0) and (b<>0) do
   if a>b then 
      a:= a mod b
   else 
      b:= b mod a;
 
Nod:= a or b;
end;
 
begin
read (a,b);
writeln (Nod(a,b));
end.

Задача: вычислить НОК (a,b)
Решение: НОК – наименьшее общее кратное двух целых чисел (такое минимальное число, которое делится как на первое, так и на второе число). Например, НОК(12,15) = 60. Существует формула нахождения НОК(a,b): НОК(a,b)=(a*b)/НОД(a,b).

НОК – всегда натуральное число, поэтому НОК(5,0) – не существует, т.к. на ноль делить нельзя.

C++

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 #include <iostream>
 
int Nod (int a, int b)
{
    while (a && b)
           if (a>b) 
                     a%=b;
           else 
                     b%=a;
 
    return a|b;
}
 
 
int Nok (int a, int b)
{
    if (!a || !b) 
              return -1;
    else 
              return (a*b)/Nod(a,b);
}
 
int main()
{
    int a,b;
    std:: cin >> a >> b;
 
    std:: cout << Nok (a,b) << "\n";
    system  ("pause");
    return 0;
}

Pascal

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 var a,b: longint;
 
function Nod (a,b: longint): longint;
begin
 
while (a<>0) and (b<>0) do
        if a>b then 
           a:= a mod b
        else
           b:= b mod a;
 
Nod:= a or b;
end;
 
 
function Nok (a,b: longint): longint;
begin
if (a=0) or (b=0) then 
   Nok:= -1
else
   Nok:= (a*b) div Nod(a,b);
end;
 
begin
read (a,b);
 
writeln (Nok(a,b));
end.

Однако, при нахождении НОК, могут получаться довольно большие числа, поэтому необходимо применять китайскую теорему об остатках:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 #include <iostream>
 
int Nod (int a, int b)
{
    while (a && b)
        if (a>b) 
                         a%=b;
        else
                         b%=a;
 
    return a|b;
}
 
 
int Nok (int a, int b)
{
    if (!a || !b) 
              return -1;
    else
              return (a/Nod(a,b))*b;
}
 
int main()
{
    int a,b;
    std:: cin >> a >> b;
    std:: cout << Nok (a,b) << "\n";
    system  ("pause");
    return 0;
}

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 var a,b: longint;
 
function Nod (a,b: longint): longint;
begin
 
while (a<>0) and (b<>0) do
   if a>b then 
       a:= a mod b
   else
       b:= b mod a;
 
Nod:= a or b;
end;
 
 
function Nok (a,b: longint): longint;
var tmp: longint;
begin
if (a=0) or (b=0) then Nok:= -1
 
else begin
    tmp:= Nod (a,b);
    Nok:= (a div tmp)*b;
end;
 
end;
 
begin
read (a,b);
writeln (Nok(a,b));
end.

И типы данных int64 в Pascal, _int64 в C++.

Метки c++, нод, нок, фактоиал

Размещено в По теме программирования

Главная страница

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

Всего комментариев 13

Комментарии

	Ты бы коды отформатировал аккуратно чтоли...
	Запись от Evg размещена 12.02.2012 в 13:14

	Извиняюсь за такой стиль: давно он у меня уже, и свыкся с ним я)
	Запись от Dani размещена 12.02.2012 в 13:18

> Извиняюсь за такой стиль: давно он у меня уже, и свыкся с ним я)

Ты для себя пишешь или для других? Если для себя - оставляй как есть, если для других - то было бы полезно переделать к тому виду, который будет понятен людям. Особенно начинающим, т.к. статья ориентирована на них

Запись от Evg размещена 15.02.2012 в 19:43 Evg вне форума

	какой максимальный факториал, который может уместиться в 31/32/63/64 бита?
	Запись от turbanoff размещена 16.02.2012 в 12:54

	Для 31\32: 479001600 или 12! Для 63\64: 2432902008176640000 или 20!
	Запись от Dani размещена 17.02.2012 в 21:27

Факториал отрицательного значения приведёт к зацикливанию программы(попробуй ввести -2)
Вот простая рекурсивная функция для его вычисления

C++ (Qt)
1
2
3
4
5
6
7
unsigned long fact(unsigned long n)
{
    unsigned long ret = ((n == 0) ? (n = 1) : n);
    if(1 < (n = n - 1))
        ret = ret*fact(n);
    return ret;
}

Ниже лаконичный алгоритм для факториала с проверкой корректности ввода

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
 
unsigned long fact(unsigned long n)
{
    unsigned long ret = ((n == 0) ? (n = 1) : n);
    if(1 < (n = n - 1))
        ret = ret*fact(n);
    return ret;
}
 
 
int main()
{
    unsigned long n;
    while(true)
    {
        cout<<"Enter n : ";
        if(!(cin>>n))
            cout<<"Input error\n";
        else
            cout<<"n! = "<<fact(n)<<endl;;
    }
    return 0;
}

Отработка алгоритма
Enter n : 0
n! = 1
Enter n : 1
n! = 1
Enter n : 5
n! = 120
Enter n : 10
n! = 3628800
Enter n :

Запись от -=ЮрА=- размещена 02.04.2012 в 19:48 -=ЮрА=- вне форума

Факториал определён только для целых неотрицательных чисел. А проверка - это уже добавочное. В идеале надо проверять на корректность ввода: вводить сткорой, смотреть есть ли символы или через исключения и т.д. Я написал самое основное, это предполагает корректный ввод. Остальные "фишки" остаются пользователю

Запись от Dani размещена 12.04.2012 в 23:59 Dani вне форума

	да и ваша программа зацикливается, если ввести a
	Запись от Dani размещена 13.04.2012 в 00:01

Dani, введи 150 и понаблюдай за своим факториалом...
На счёт зацикливания

C++
1
2
3
4
5
6
if(!(cin>>n) || cin.get() != '\n')
{
   cin.sync();
   cin.clear();
   cout<<"Input error\n";
}

Запись от -=ЮрА=- размещена 03.05.2012 в 13:07 -=ЮрА=- вне форума

Но бывают случаи, когда необходимо вычислить, например 1000!. В этом случае, прибегают к использованию длинной арифметики. «Длинная арифметика — в вычислительной технике операции над числами, разрядность которых превышает длину машинного слова данной вычислительной машины», - говорит нам Википедия.

Это описано выше.

Запись от Dani размещена 03.05.2012 в 22:06 Dani вне форума

	Для автора этого блога(все остальные проходите мимо!) Dani , потом удалишь эту запись Ссылка для скачивания файла: http://rusfolder.com/32756563 я неуверен что ЛС форума быстра, поэтому сюда запостил
	Запись от -=ЮрА=- размещена 21.09.2012 в 19:19

	Если требуется вычислить N! при N>1000 ... А что мешает сначала вычислить lg(N!)? Вы получите порядок числа (ну и мантиссу)
	Запись от echs размещена 07.11.2015 в 16:32

	Меня вот что интересует. Давно ли в паскале вместо сложения стали писать OR? Nod:= a or b; (!!) - ЭТО ВАШ КОД.
	Запись от echs размещена 27.06.2016 в 20:49

Новые блоги и статьи Все статьи Все блоги /
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .

Сообщение форума

Отменить изменения