Форум программистов, компьютерный форум, киберфорум
Dani
Войти
Регистрация
Восстановить пароль
Рейтинг: 4.83. Голосов: 6.

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

Запись от Dani размещена 12.02.2012 в 12:47
Обновил(-а) Dani 15.02.2012 в 20:17

Часто приходится наблюдать вопросы\просьбы насчет довольно тривиальные функции. Т.к. это старая тема, я решил все, что придумаю собрать сюда. При нахождении ошибок и предложений, прошу сообщать в ЛС. И так, поехали:
Задача: вычислить 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++.
Просмотров 19675 Комментарии 13
Всего комментариев 13
Комментарии
  1. Старый комментарий
    Аватар для Evg
    Ты бы коды отформатировал аккуратно чтоли...
    Запись от Evg размещена 12.02.2012 в 13:14 Evg вне форума
  2. Старый комментарий
    Извиняюсь за такой стиль: давно он у меня уже, и свыкся с ним я)
    Запись от Dani размещена 12.02.2012 в 13:18 Dani вне форума
  3. Старый комментарий
    Аватар для Evg
    > Извиняюсь за такой стиль: давно он у меня уже, и свыкся с ним я)

    Ты для себя пишешь или для других? Если для себя - оставляй как есть, если для других - то было бы полезно переделать к тому виду, который будет понятен людям. Особенно начинающим, т.к. статья ориентирована на них
    Запись от Evg размещена 15.02.2012 в 19:43 Evg вне форума
  4. Старый комментарий
    Аватар для turbanoff
    какой максимальный факториал, который может уместиться в 31/32/63/64 бита?
    Запись от turbanoff размещена 16.02.2012 в 12:54 turbanoff вне форума
  5. Старый комментарий
    Для 31\32: 479001600 или 12!
    Для 63\64: 2432902008176640000 или 20!
    Запись от Dani размещена 17.02.2012 в 21:27 Dani вне форума
  6. Старый комментарий
    Факториал отрицательного значения приведёт к зацикливанию программы(попробуй ввести -2)
    Вот простая рекурсивная функция для его вычисления
    [CPPQT]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;
    }[/CPPQT]

    Ниже лаконичный алгоритм для факториала с проверкой корректности ввода
    [CPPQT]#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;
    }[/CPPQT]
    [B]Отработка алгоритма[/B]
    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 -=ЮрА=- вне форума
  7. Старый комментарий
    Факториал определён только для целых неотрицательных чисел. А проверка - это уже добавочное. В идеале надо проверять на корректность ввода: вводить сткорой, смотреть есть ли символы или через исключения и т.д. Я написал самое основное, это предполагает корректный ввод. Остальные "фишки" остаются пользователю
    Запись от Dani размещена 12.04.2012 в 23:59 Dani вне форума
  8. Старый комментарий
    да и ваша программа зацикливается, если ввести a
    Запись от Dani размещена 13.04.2012 в 00:01 Dani вне форума
  9. Старый комментарий
    Dani, введи 150 и понаблюдай за своим факториалом...
    На счёт зацикливания
    [CPP]if(!(cin>>n) || cin.get() != '\n')
    {
    cin.sync();
    cin.clear();
    cout<<"Input error\n";
    }[/CPP]
    Запись от -=ЮрА=- размещена 03.05.2012 в 13:07 -=ЮрА=- вне форума
  10. Старый комментарий
    Цитата:
    Но бывают случаи, когда необходимо вычислить, например 1000!. В этом случае, прибегают к использованию длинной арифметики. «Длинная арифметика — в вычислительной технике операции над числами, разрядность которых превышает длину машинного слова данной вычислительной машины», - говорит нам Википедия.
    Это описано выше.
    Запись от Dani размещена 03.05.2012 в 22:06 Dani вне форума
  11. Старый комментарий
    [SPOILER="Для автора этого блога(все остальные проходите мимо!)"][B]Dani [/B], потом удалишь эту запись
    Ссылка для скачивания файла: [url]http://rusfolder.com/32756563[/url]
    я неуверен что ЛС форума быстра, поэтому сюда запостил[/SPOILER]
    Запись от -=ЮрА=- размещена 21.09.2012 в 19:19 -=ЮрА=- вне форума
  12. Старый комментарий
    Если требуется вычислить N! при N>1000 ...
    А что мешает сначала вычислить lg(N!)?
    Вы получите порядок числа (ну и мантиссу)
    Запись от echs размещена 07.11.2015 в 16:32 echs вне форума
  13. Старый комментарий
    Меня вот что интересует.
    Давно ли в паскале вместо сложения стали писать OR?
    Nod:= a or b; (!!) - ЭТО ВАШ КОД.
    Запись от echs размещена 27.06.2016 в 20:49 echs вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.