90 / 46 / 8
Регистрация: 08.10.2008
Сообщений: 437
1

5 одновременно запущенных экземпляров функции

01.03.2021, 17:15. Показов 1601. Ответов 12

Author24 — интернет-сервис помощи студентам
Всем привет! Наткнулся на один пример по рекурсивной функции в обучающей программе.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int factorial(int num);
int main(){
    int x = 5;
    printf("The factorial %d is %d\n", x, factorial(x));
return 0;
}
int factorial(int num){
    if (num==1)
        return(1);
    else
        return(num*factorial(num-1));
}
И возник вопрос. А это, вообще, нормально так факториал вычислять? А если надо будет так вычислить факториал 1000? Может быть тогда все же лучше циклом воспользоваться? Или там не особо памяти уйдет на такое действие?

P.S. за одно, раз уж пишу, поделитесь пожалуйста способами выяснить сколько программа на си потребляет ОЗУ и ЦП?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.03.2021, 17:15
Ответы с готовыми решениями:

Количество запущенных экземпляров программы
Как в VB6 проверять, запущена уже эта программа или нет? Если экземпляр уже запущен, то...

Два одновременно запущенных процесса
Привет, программеры. Вопрос у мня по одному моменту в БАТнике. Дело такое: мне нужно в...

Динамический массив экземпляров класса, с неизвестным количеством экземпляров
Доброго времени суток. По ходу работы, программно должны создаваться и удаляться объекты класса....

В классе данных определите переменные экземпляров.Значения переменных экземпляров должны быть введены с клавиатуры
В классе данных определите переменные экземпляров.Значения переменных экземпляров должны быть...

12
1287 / 880 / 254
Регистрация: 30.06.2015
Сообщений: 4,592
Записей в блоге: 51
01.03.2021, 17:41 2
Циклом быстрее по любому. Рекурсию на практике применяют, когда не важна скорость вычислений, для упрощения кода. Рекурсия просто ужасно медленна. Рекурсивные функции зависят от глубины стека программы, который обычно не сильно глубок. Сколько памяти потребляет программа можно узнать запустив системный монитор.
1
Заблокирован
01.03.2021, 20:30 3
Цитата Сообщение от SashaRasha Посмотреть сообщение
А это, вообще, нормально так факториал вычислять?
В таких языках как Си - нет.
Рекурсия порождает дерево вызовов и уже на 100! рекурсия начнёт тупить, а на 200! уже загнётся

Самый простой способ - это цикл.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
]int 
main(void) {
    
    unsigned k = 1;
    unsigned char factorial_number = 10;
    
    
    for (int i = 2; i <= factorial_number; i++) {
         k *= i;
        
    }
    
    printf("%d", k);
 
    return 0;
}
нужно только понимать, что если произойдёт переполнение типа, то ответ будет неверным.

Ну а в языках типа Lisp, где рекурсия это основа всего, можно спокойно использовать рекурсию. Особенно если она хвостовая.
Lisp
1
2
3
4
5
6
7
8
9
(defn fuct [num]
  ((fn [acc init]
     (if (> init num)
       acc
       (recur (*' acc init) (inc init)))) 1 2))
 
(println (fuct 100))
 
=>93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000N
2
Модератор
Эксперт функциональных языков программированияЭксперт Python
36590 / 20320 / 4218
Регистрация: 12.02.2012
Сообщений: 33,621
Записей в блоге: 13
01.03.2021, 20:45 4
Лучший ответ Сообщение было отмечено easybudda как решение

Решение

Цитата Сообщение от CoderHuligan Посмотреть сообщение
Рекурсия просто ужасно медленна.
- далеко не всегда.
Цитата Сообщение от SashaRasha Посмотреть сообщение
А если надо будет так вычислить факториал 1000?
- вычислить факториал 1000 будет трудно по другой причине. Ты представляешь, КАКОЕ это число?

Вот рекурсивная (!) программа на Питоне (он в несколько раз "медленнее" С), которая молниеносно вычисляет 500!

Python
1
2
3
4
5
6
7
def fact(n,s=1):
    if (n==1):
        return s
    else:
        return fact(n-1,s*n)
        
print(fact(500))
А вот результат:

Кликните здесь для просмотра всего текста

12201368259911100687012387854230469262535743428031928421924135883858453731538819 97605496447502203281863013616477148203
58416337872207817720048078520515932928547790757193933060377296085908627042917454 78824249127263443056701732707694610628
02310452644218878789465754777149863494367781037644274033827365397471386477878495 43848959553753799042324106127132698432
77457155463099772027810145610811883737095310163563244329870295638966289116589747 69572087926928871281780070265174507768
41071962439039432253642260523494585012991857150124870696156814162535905669342381 30088562492468915641267756544818865065
93847951775360894005745238940335798476363944905313062323749066445048824665075946 73586207463792518420045936969298102226
39719525971909452178233317569345815085523328207628200234026269078983424517120062 07714640979456116127629145951237229913
34016955236385094288559201872743379517301458635757082835578015873543276888868012 03998823847021514676054454076635359841
74430480128938313896881639487469658817504506926365338175055478128640000000000000 00000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000


Что же до 1000!, то вычислить его рекурсивно не так просто (не хватает стандартного стека). Но для представления себе порядка этого числа, его можно вычислить циклом:

Кликните здесь для просмотра всего текста

40238726007709377354370243392300398571937486421071463254379991042993851239862902 05920442084869694048004799886101971960
58631666872994808558901323829669944590997424504087073759918823627727188732519779 50595099527612087497546249704360141827
80946464962910563938874378864873371191810458257836478499770124766328898359557354 32513185323958463075557409114262417474
34934755342864657661166779739666882029120737914385371958824980812686783837455973 17461360853795345242215865932019280908
78297308431392844403281231558611036976801357304216168747609675871348312025478589 32076716913244842623613141250878020800
02616831510273418279777047846358681701643650241536913982812648102130927612448963 59928705114964975419909342221566832572
08082133318611681155361583654698404670897560290095053761647584772842188967964624 49451607653534081989013854424879849599
53319101723355556602139450399736280750137837615307127761926849034352625200015888 53514733161170210396817592151090778801
93931781141945452572238655414610628921879602238389714760885062768629671466746975 62911234082439208160153780889893964518
26324367161676217916890977991190375403127462228998800519544441428201218736174599 26429565817466283029555702990243241531
81617210465832036786906117260158783520751516284225540265170483304226143974286933 06169089796848259012545832716822645806
65267699586526822728070757813918581788896522081643483448259932660433676601769996 12831860788386150279465955131156552036
09398818061213855860030143569452722420634463179746059468257310379008402443243846 56572450144028218852524709351906209290
23136493273497565513958720559654228749774011413346962715422845862377387538230483 86568897646192738381490014076731044664
02598994902222217659043399018860185665264850617997023561938970178600408118897299 18311021171229845901641921068884387121
85564612496079872290851929681937238864261483965738229112312502418664935314397013 74285319266498753372189406942814341185
20158014123344828015051399694290153483077644569099073152433278288269864602789864 32113908350621709500259738986355427719
67428222487575867657523442202075736305694988250879689281627538488633969099598262 80956121450994871701244516461260379029
30912088908694202851064018215439945715680594187274899809425474217358240106367740 45957417851608292301353580818400969963
72524230560855903700624271243416909004153690105933983835777939410970027753472000 00000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000


В 32-х битной среде максимальное значение, которое уместится в стандартный знаковый int - это скромное 10!=3628800
Значениe 11! уже выйдет за пределы разрядной сетки. И, как это ни странно, в реальных программах не нужно вычислять факториал при каждой необходимости. Гораздо рациональнее поступить так: вычислить один раз (естественно, циклом) весь массив факториалов:

C
1
2
3
4
     int fact[11];
     int i,p;
     fact[0]=1 ;
     for (i=1; i<11; i++) fact[i]=i*fact[i-1];
и далее вместо студиозно-тупенького вычисления k=fact(n); писать k=fact[n];
2
90 / 46 / 8
Регистрация: 08.10.2008
Сообщений: 437
01.03.2021, 23:04  [ТС] 5
Цитата Сообщение от Catstail Посмотреть сообщение
Вот рекурсивная (!) программа на Питоне (он в несколько раз "медленнее" С), которая молниеносно вычисляет 500!
Ну на питоне, вообще, все просто
Python
1
2
import math
math.factorial(1000)
А на си нашел такое решение
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <gmp.h>
static void
factorial (long n, mpz_t r){
  mpz_init_set_si (r, 1);
  for (; n > 1; n--){
    mpz_mul_si (r, r, n);
  }
}
 
int main(void){
  int n;
  mpz_t r;
  while (scanf ("%d", &n) == 1){
    factorial (n, r);
    gmp_printf ("%Zd\n", r);
  }
  return 0;
}
Плохо понимаю что, конкретно, выполняют строки 5 и 7, но считает не хуже "питоши". Какой-то внятный гайд по gmp не нашел. Знаю только что компилировать нужно с параметром
Bash
1
gcc -lgmp
остается только курить мануал
0
Вездепух
Эксперт CЭксперт С++
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
01.03.2021, 23:41 6
Цитата Сообщение от SashaRasha Посмотреть сообщение
А это, вообще, нормально так факториал вычислять?
Нет, в С - не нормально.

(Как не нормально и располагать функции в файле снизу вверх, что приводит дублированию объявлений без явной на то необходимости.)

Цитата Сообщение от SashaRasha Посмотреть сообщение
А если надо будет так вычислить факториал 1000? Может быть тогда все же лучше циклом воспользоваться?
Лучше.

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

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
factorial:
        mov     eax, 1
        cmp     edi, 1
        je      .L4
.L5:
        mov     edx, edi
        sub     edi, 1
        imul    eax, edx
        cmp     edi, 1
        jne     .L5
.L4:
        ret
https://godbolt.org/z/TWa8oT

То есть никакой рекурсии не будет и никаких "одновременно запущенных экземпляров функции" не будет тоже.
2
Заблокирован
02.03.2021, 00:09 7
SashaRasha, если и использовать рекурсию, то хвостовую, без отложенных вычислений, где все расчёты производятся на месте и функции известны параметры сразу.

Вот примерно то же самое, что я написал на Lisp, только на С

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
int
factorial(int acc, int init, int num) {
    
    if(init > num) {
        return acc;
    }
    
    factorial(acc * init,  init + 1, num);
    
}
 
 
int 
main(void) {
    
    printf("%d", factorial(1, 2, 5));
 
    return 0;
}
1
200 / 236 / 33
Регистрация: 29.03.2019
Сообщений: 667
02.03.2021, 00:26 8
Цитата Сообщение от SashaRasha Посмотреть сообщение
А это, вообще, нормально так факториал вычислять?
Это бездумная калька математической нотации: https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=\begin{cases}1 & \text{ if } n=1  \\ f(n-1) & \text{ if } n>1  \end{cases}, \, n \in \mathbb{N}
Цитата Сообщение от SashaRasha Посмотреть сообщение
поделитесь пожалуйста способами выяснить сколько программа на си потребляет ОЗУ и ЦП?
Касательно операционных систем: если говорить грубо, то ровно столько, сколько вы запросили памяти у своей программы, а порцессорное время зависит от приоритета запущенной программы. Если точно -- то вышесказанное + системные расходы на создание и обслуживание процесса. Например
Bash
1
2
~% ps ax -o pid,user,%mem,command | grep <progname>
# pmap pid
Процессорное время можно узнать с помощью утилиты time.
Где же ОС отсутствует, то как говорится всё сам ручками.
Цитата Сообщение от SashaRasha Посмотреть сообщение
но считает не хуже "питоши"
Не хуже не может быть по определению.
1. в питоше используется именно gmp
2. python как динамически типизированный интерпретируемый язык делает кучу всякой работы, которая в си-примере отсутствует.
Цитата Сообщение от SashaRasha Посмотреть сообщение
Какой-то внятный гайд по gmp не нашел. Знаю только что компилировать нужно с параметром
Параметр -l говорит линковщику что искомые функции находятся в динамической библиотеке libgmp.so.
Параметр -l: скажет линковщику искать статическую библиотеку. Документация по GMP вполне вменяема и полностью понятна, какие еще гайды вам нужны?

Добавлено через 9 минут
Цитата Сообщение от zeroalef Посмотреть сообщение
1. в питоше используется именно gmp
Я не знаю откуда я это выдумал, но похоже что это неправда. И есть binding для python.
2
Модератор
Эксперт функциональных языков программированияЭксперт Python
36590 / 20320 / 4218
Регистрация: 12.02.2012
Сообщений: 33,621
Записей в блоге: 13
02.03.2021, 07:09 9
Цитата Сообщение от SashaRasha Посмотреть сообщение
Ну на питоне, вообще, все просто
- это не решение. Когда тебе дают задачу, то предполагают, что ты реализуешь решение, а не найдешь подходящий библ. вызов (последнее требует только памяти).
1
90 / 46 / 8
Регистрация: 08.10.2008
Сообщений: 437
02.03.2021, 11:21  [ТС] 10
В общем, немного разобрался.
C
1
mpz_init_set_si (r, 1); //тут инициализируется переменная r, как signed integer и присваивается значение 1.
C
1
mpz_mul_si (r, r, n); //а тут что-то типа r*=n
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
36590 / 20320 / 4218
Регистрация: 12.02.2012
Сообщений: 33,621
Записей в блоге: 13
02.03.2021, 20:16 11
Вот вычисление 1000! на чистом 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
 
void factorials(int n)
{
     char buf[5000];
     int i,j,p,s,k;
     
     for (i=1; i<5000; i++) buf[i]=' ';
     buf[4999]='1';
     
     for (i=1; i<=n; i++)
     {
         p=0;
         j=4999;
         while(1)
         {
             if (buf[j]==' ') 
             {
                if (p !=0) 
                {
                   buf[j--]=p%10+'0';
                   p=p/10;
                }
                else
                   break;
             }
             else
             {                        
                s=buf[j]-'0';
                s=p+s*i;
                buf[j]=s%10+'0';
                p=s/10;
                j--;
             }   
         }    
     }
 
     for (k=j; k<5000; k++) printf("%c",buf[k]);
     printf("\n");
    
}
 
int main(int argc, char *argv[])
{
 
  factorials(1000); 
  
  return 0;
}
Результат:

Кликните здесь для просмотра всего текста

40238726007709377354370243392300398571937486421071463254379991042993851239862902 0592044208486969404800479988610197196
05863166687299480855890132382966994459099742450408707375991882362772718873251977 95059509952761208749754624970436014182
78094646496291056393887437886487337119181045825783647849977012476632889835955735 43251318532395846307555740911426241747
43493475534286465766116677973966688202912073791438537195882498081268678383745597 31746136085379534524221586593201928090
87829730843139284440328123155861103697680135730421616874760967587134831202547858 93207671691324484262361314125087802080
00261683151027341827977704784635868170164365024153691398281264810213092761244896 35992870511496497541990934222156683257
20808213331861168115536158365469840467089756029009505376164758477284218896796462 44945160765353408198901385442487984959
95331910172335555660213945039973628075013783761530712776192684903435262520001588 85351473316117021039681759215109077880
19393178114194545257223865541461062892187960223838971476088506276862967146674697 56291123408243920816015378088989396451
82632436716167621791689097799119037540312746222899880051954444142820121873617459 92642956581746628302955570299024324153
18161721046583203678690611726015878352075151628422554026517048330422614397428693 30616908979684825901254583271682264580
66526769958652682272807075781391858178889652208164348344825993266043367660176999 61283186078838615027946595513115655203
60939881806121385586003014356945272242063446317974605946825731037900840244324384 65657245014402821885252470935190620929
02313649327349756551395872055965422874977401141334696271542284586237738753823048 38656889764619273838149001407673104466
40259899490222221765904339901886018566526485061799702356193897017860040811889729 91831102117122984590164192106888438712
18556461249607987229085192968193723886426148396573822911231250241866493531439701 37428531926649875337218940694281434118
52015801412334482801505139969429015348307764456909907315243327828826986460278986 43211390835062170950025973898635542771
96742822248757586765752344220207573630569498825087968928162753848863396909959826 28095612145099487170124451646126037902
93091208890869420285106401821543994571568059418727489980942547421735824010636774 04595741785160829230135358081840096996
37252423056085590370062427124341690900415369010593398383577793941097002775347200 00000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000
1
594 / 286 / 178
Регистрация: 06.06.2016
Сообщений: 547
03.03.2021, 00:21 12
Цитата Сообщение от SashaRasha Посмотреть сообщение
Какой-то внятный гайд по gmp не нашел
GMP (The GNU Multiple Precision Arithmetic Library) — библиотека, написанная на Си, предназначенная для вычислений с плавающей запятой, целыми и рациональными числами с произвольной точностью.

Разрабатывается с 1993 г, последний релиз — 2020 г. Толково написана, быстрая. В её разработке, помимо прочих, принимали (принимают?) участие такие личности, как Richard Stallman и Paul Zimmermann.

Официальный мануал:
https://gmplib.org/gmp-man-6.2.1.pdf
2
Модератор
Эксперт функциональных языков программированияЭксперт Python
36590 / 20320 / 4218
Регистрация: 12.02.2012
Сообщений: 33,621
Записей в блоге: 13
03.03.2021, 11:50 13
А вот вычисление 1000! на чистом С хвостовой рекурсией:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
 
void factorials(int n,char *buf)
{
     int i,j,p,s,k;
     
     if (n==0) return;
     
     p=0;
     j=4999;
 
     while(1)
     {
         if (buf[j]==' ') 
         {
            if (p !=0) 
            {
               buf[j--]=p%10+'0';
               p=p/10;
            }
            else
               break;
         }
         else
         {                        
            s=buf[j]-'0';
            s=p+s*n;
            buf[j]=s%10+'0';
            p=s/10;
            j--;
         }   
     }    
 
     factorials(n-1,buf);
    
}
 
int main(int argc, char *argv[])
{
 
  int i;
  char buf[5000];
  
  for (i=1; i<5000; i++) buf[i]=' ';
  buf[4999]='1';
 
  factorials(1000,buf); 
  
  for (i=1; i<5000; i++) if (buf[i]!=' ') printf("%c",buf[i]);
  
  return 0;
}
Как и писал выше TheCalligrapher, компилятор хвостовую рекурсию распознал.
2
03.03.2021, 11:50
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.03.2021, 11:50
Помогаю со студенческими работами здесь

Как запустить несколько экземпляров функции
Здравствуйте! Я хочу запускать несколько экземпляров функции Pi_num__idea2 с разными параметрами,...

Реализовать базовый и производный классы. В главной функции создать несколько экземпляров каждого класса и протестироват
Создать класс тройки чисел. Определить конструкторы, деструктор, функции доступа к полям, ввода...

Обработать ошибку, возникающую при вызове функции GetObject в случае, когда нет доступных экземпляров объекта
на строке Set wa = GetObject(, &quot;Word.Application&quot;) выдает ошибку Run-time error 429; ActiveX...

Сравнение двух различных экземпляров класса внутри функции класса
#include &lt;iostream&gt; #include &lt;string&gt; using namespace std; class Backpack { private: int...

Можно ли использовать self и $this в одной функции одновременно?
class A { private static $a; public $b=1; public function arr($a) { self::$a=$a;...

Выполнение функции одновременно с нажатием на ссылку
Есть ссылка на сайте. Клик по ней приволит к открытию страницы. Как реализовать чтобы при клике...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru