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

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

Показов 63022 Комментарии 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

Новые блоги и статьи Все статьи Все блоги /
Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .

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

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