Форум программистов, компьютерный форум, киберфорум
Free Pascal
Форум программистов и сисадминов Киберфорум > Форум программистов > Pascal (Паскаль) > Free Pascal
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
1

Рекурсия

07.06.2012, 20:48. Показов 1119. Ответов 10
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Решить задачу AB mod C.
Цикл слишком медленный, значит, я хотел бы её решить рекурсивным методом. Но что-то не получается! Вот медленный метод. Работает с файлами. Напишите 3 2 4, должно выдать 1, а при 2 10 1000 - 24. Но, ничего не получается.
Вот слабое решение:
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

var
  a, b, c: uint64;
  i, o: text;
 
function ostat(a, b, c: uint64): uint64;
var
  i: longint;
  o: uint64;
begin
  o := 1;
  for i := 1 to b do
    o := o * a mod c;
  ostat := o;
end;
 
begin
  assign(i, 'input.txt');
  assign(o, 'output.txt');
  reset(i); rewrite(o);
  while not EoF(i) do
  begin
    readln(i, a, b, c);
    writeln(o, ostat(a, b, c));
  end;
  close(i); close(o);
end.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 07.06.2012, 20:48
Ответы с готовыми решениями:

Рекурсия в Pascal
Привет, товарищи. Слезно прошу вашей помощи в понимании рекурсии. Ниже у меня есть программка,...

Процедуры и функции. Рекурсия
Нужна помощь в составе программы для Free Паскаль. Я вообще в этом не разбираюсь

Перебор или рекурсия...
Есть некий массив. Нужно по первому столбику узнать сколько минимально строк нужно вычеркнуть,...

Ханойские башни. Рекурсия
Пояснения к программе Самое простое и известное решение строится в виде рекурсивной процедуры...

10
36 / 36 / 28
Регистрация: 17.01.2012
Сообщений: 64
08.06.2012, 00:04 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var
  a, b, c: uint64;
  i, o: text;
function ostat(a, b: uint64): uint64;
var
  i: longint;
  o: uint64;
begin
  if b = 0 then ostat:=1
    else ostat:=ostat(a,b-1)*a;
end;
 
begin
  assign(i, 'input.txt');
  assign(o, 'output.txt');
  reset(i); rewrite(o);
  while not EoF(i) do
  begin
    readln(i, a, b, c);
    writeln(o, ostat(a, b) mod c);
  end;
  close(i); close(o);
end.
0
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
08.06.2012, 00:55 3
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

type long=array[0..1000333]of longint;
Var x,h,ans,c:int64;
    n,b:long;
    i,j:longint;
    q:char;
    s:ansistring;
 function decc(a:long):long;
   var i:longint;
     begin
       dec(a[1]);
       for i:=2 to a[0] do
         begin
           if a[i-1]<0 then begin
                              inc(a[i-1],10);
                              dec(a[i]);
                            end;
         end;
       if a[a[0]]=0 then dec(a[0]);
       decc:=a;
     end;
 function readlong(s:ansistring):long;
   var i:longint;
       p:integer;
       c:long;
     begin
       fillchar(c,sizeof(c),0);
       c[0]:=length(s);
       for i:=1 to length(s) do
         val(s[i],c[c[0]-i+1],p);
       readlong:=c;
     end;
 function modd(a:long;b:int64):int64;
   var ost:int64;
      i:longint;
     begin
       ost:=0;
       for i:=a[0] downto 1 do
         ost:=(ost*10+a[i]) mod b;
       modd:=ost;
     end;
  begin
    s:='';
    read(q);
    while q<>' ' do
      begin
        s:=s+q;
        read(q);
      end;
    b:=readlong(s);
    read(q);
    s:='';
    while q<>' ' do
      begin
        s:=s+q;
        read(q);
      end;
    n:=readlong(s);
    readln(c);
    h:=modd(b,c);
    ans:=modd(decc(b),c);
    n:=decc(n);
    for i:=1 to n[0] do
      begin
        x:=1;
        for j:=1 to n[i] do
          x:=(x*h) mod c;
        ans:=ans*x mod c;
        h:=h*h mod c;
        x:=h;
        for j:=2 to 5 do
          h:=h*x mod c;
      end;
    if ans=0 then ans:=c;
    Writeln(ans);
  end.
http://codeforces.ru/blog/entry/451 это похожая задачи, посмотрите Задача D. Блокнот
0
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
09.06.2012, 14:20  [ТС] 4
Ни один вариант не сработал
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
09.06.2012, 17:00 5
SeryZone, ссылку на задачу дайте.
0
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
10.06.2012, 01:07 6
прочитайте тот разбор http://codeforces.ru/blog/entry/451,+ там есть исходники
0
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
10.06.2012, 15:26  [ТС] 7
http://www.e-olimp.com/problems/1121. Вот

Добавлено через 1 минуту
http://www.e-olimp.com/problems/480 И эта
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
10.06.2012, 16:05 8
Лучший ответ Сообщение было отмечено как решение

Решение

SeryZone, Я объясню как быстро найти необходимый результат, сами попробуйте его реализовать (если не будет получаться, то выкладывайте что получилось, помогу).
В общем число a^68 mod b можно находить так:
Pascal
1
2

a:=a mod b;
res:=a;
и 67 раз повторить такую операцию:
Pascal
1

res:=(res*a) mod b;
А можно так (по моему это называется бинарное возведение в степень):
Pascal
1
2
3

a:=a mod b;
res:=1;
tmp:=a;//в tmp сейчас a^1 mod b;
Далее так:
Pascal
1
2
3
4
5
6

tmp:=(tmp*tmp) mod b;// в tmp сейчас a^2 mod b;
tmp:=(tmp*tmp) mod b;// в tmp сейчас a^4 mod b;
tmp:=(tmp*tmp) mod b;// в tmp сейчас a^8 mod b;
tmp:=(tmp*tmp) mod b;// в tmp сейчас a^16 mod b;
tmp:=(tmp*tmp) mod b;// в tmp сейчас a^32 mod b;
tmp:=(tmp*tmp) mod b;// в tmp сейчас a^64 mod b;// теперь останавливаемся т.к. следующая степень уже больше 68.
Теперь:
Pascal
1
2
3
4
5

res:=(res*tmp) mod b; 
// теперь осталось возвести в (68-64=4) степень, т.е. осталось res домножить на a^4 mod b
tmp:=a;//в tmp сейчас a^1 mod b;
tmp:=(tmp*tmp) mod b;// в tmp сейчас a^2 mod b;
tmp:=(tmp*tmp) mod b;// в tmp сейчас a^4 mod b;// теперь останавливаемся т.к. следующая степень уже больше 4.
Теперь:
Pascal
1
2

res:=(res*tmp) mod b; 
// теперь осталось возвести в (4-4=0) степень, т.е. совсем останавливаемся и выводим результат res.
Итого в первом варианте потребовалось провести операцию: res:=(res*a) mod b; 67 раз,
А во втором варианте потребовалось провести похожую операцию: tmp:=(tmp*tmp) mod b; всего 8 раз.
При больших b разница по времени будет очень ощутима.
1
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
12.06.2012, 07:35  [ТС] 9
Спасибо, спасибо большое. Если честно, подумывал над таким алгоритмом.

Добавлено через 17 минут
One problem: Я начал решать на С++, на нём лучше, посмотрите код, вообще какую-то ерунду выдаёт!
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

#include <stdio.h>
long long ost=1,tmp;
unsigned long long a,b,c;
long i;
long long Ost(unsigned long long a,unsigned long long b,unsigned long long c)
{       
    __int64 s=1;
    tmp=ost;
    while (s<=b)
    {
        tmp=(tmp*tmp) % c;
        b/=2; s*=2;
    }   
    ost=ost*tmp;
    if (b>=2) Ost(a,b,c);
        if (b>0){ for (int i=1;i<=b;i++)
            ost=(ost*a)%c; }
    return ost;
}
int main()
{   
    scanf("%I64d%I64d%I64d",&a,&b,&c);
    ost=a;
    printf("%I64d\n",Ost(a,b,c));
}
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
12.06.2012, 12:53 10
Цитата Сообщение от SeryZone Посмотреть сообщение
Я начал решать на С++, на нём лучше, посмотрите код, вообще какую-то ерунду выдаёт!
Я сначало про Ваш код:

Цитата Сообщение от SeryZone Посмотреть сообщение
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

#include <stdio.h>
long long ost=1,tmp;
unsigned long long a,b,c;
long i;
long long Ost(unsigned long long a,unsigned long long b,unsigned long long c)
{ 
 __int64 s=1;
 tmp=ost;
 while (s<=b)
 {
 tmp=(tmp*tmp) % c;
 b/=2; s*=2;
 } 
 ost=ost*tmp;
 if (b>=2) Ost(a,b,c);// вот здесь вычисляете результат по оставшейся степень с помощью функции Ost() но результат который она вернет не используете.
 if (b>0){ for (int i=1;i<=b;i++)
 ost=(ost*a)%c; }
 return ost;
}
int main()
{ 
 scanf("%I64d%I64d%I64d",&a,&b,&c);
 ost=a;
 printf("%I64d\n",Ost(a,b,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

#include <iostream>
using namespace std; 
 
int main()
 {
    long long a,b,c, mas[64][2], res;
    int i;    
    while(cin >>a>>b>>c)
    {
        res=1;
        a%=c;
        mas[1][0]=1;
        mas[1][1]=a;
        for(i=2; i<64; i++)
        {
            mas[i][0]=mas[i-1][0]*2;
            mas[i][1]=(mas[i-1][1]*mas[i-1][1])%c;
        }    
        while(b>0)
        {
            for(i=63; i>0; i--)
                if(b>=mas[i][0])
                {
                    b-=mas[i][0];
                    res*=mas[i][1];
                    res%=c;
                    break;
                }
        }
        cout<<res<<endl;    
    }
    return(0);
 }
этот код проходит все тесты 480 задачи, и 75% тестов у задачи 1121. Для задачи 1121 его нужно доработать. Там получается что C может быть очень большим (близким к 2^63), а соответственно будут попадаться такие операции (X*Y) mod C , где X и Y числа близкие к 2^63.
Попробуйте сами пока подумать как можно такие операции выполнить. Если не получится, то попозже что-нибудь придумаю.

Добавлено через 3 часа 18 минут
По проблеме выполнения операции: операции (X*Y) mod C, где X и Y числа близкие к 2^63, ничего лучшего пока не придумал, чем бинарное суммирование. Смысл такой же как и бинарное возведение в степень (которое описывал в посте №8).
При суммировании двух чисел, близких к 2^63 получается отрицательное число, из которого можно вытащить результат:
C++
1

res=((9223372036854775807)%c+(res+9223372036854775807+2)%c)%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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
using namespace std; 
long long mas1[64][2];
long long f(long long a, long long b, long long c)
{
    int i;
    long long res=0;
    mas1[1][0]=1;
    mas1[1][1]=a;
    for(i=2; i<64; i++)
    {
        mas1[i][0]=mas1[i-1][0]*2;
        mas1[i][1]=mas1[i-1][1]+mas1[i-1][1];
        if(mas1[i][1]<0)
            mas1[i][1]=((9223372036854775807)%c+(mas1[i][1]+9223372036854775807+2)%c)%c;
        else
            mas1[i][1]%=c;      
    }
    while(b>0)
    {
        for(i=63; i>0; i--)
            if(b>=mas1[i][0])
            {
                b-=mas1[i][0];
                res+=mas1[i][1];
                if(res<0)
                    res=((9223372036854775807)%c+(res+9223372036854775807+2)%c)%c;
                else
                    res%=c;
                break;
            }
    }
    return res;
}
 
int main()
{
    long long a,b,c, mas[64][2], res;
    int i;  
    while(cin >>a>>b>>c)
    {
        res=1;
        a%=c;
        mas[1][0]=1;
        mas[1][1]=a;
        for(i=2; i<64; i++)
        {
            mas[i][0]=mas[i-1][0]*2;
            if(mas[i-1][1]>3037000499)
                mas[i][1]=f(mas[i-1][1],mas[i-1][1],c);
            else
                mas[i][1]=(mas[i-1][1]*mas[i-1][1])%c;
        }   
        while(b>0)
        {
            for(i=63; i>0; i--)
                if(b>=mas[i][0])
                {
                    b-=mas[i][0];                                       
                    if(res>3037000499)
                    {
                        res=f(res,mas[i][1],c);
                    }
                    else
                        if(mas[i][1]>3037000499)
                            res=f(mas[i][1],res,c);
                        else
                        {
                            res*=mas[i][1];
                            res%=c;
                        }
                    break;
                }
        }
        cout<<res<<endl;    
    }
    return(0);
}
для задачи 1121. Кстати этот код и для задачи 480 должен подойти, но будет работать немного дольше, чем предыдущий код.
1
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
22.06.2012, 12:39  [ТС] 11
Спасибо!!! Никогда бы и не додумался. Но до сих пор я вообще ни одного ни другого кода я не понял
0
22.06.2012, 12:39
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 22.06.2012, 12:39
Помогаю со студенческими работами здесь

Фрактал рекурсия - прокомментировать код
пожалуйста прокоментируйте весь этот код, я хочу в нем разобраться. unit Unit1; {$mode...

Рекурсия. Каким будет значение f (10)?
Здравствуйте, подскажите ход решения задачи по рекурсии. (Сколько тему &quot;Рекурсивные функции&quot;...

Рекурсия, извлечение квадратного корня
ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ РЕКУРСИИ УСЛОВИЕ : Вычислить значение X = sqrt a ,...

Рекурсия. Вывод данных с помошью рекурсии.
Задача выглядит так: Разработайте рекурсивную подпрограмму, формирующую последовательность строк:...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru