Форум программистов, компьютерный форум CyberForum.ru

Рекурсивные функции. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
14.04.2011, 23:44     Рекурсивные функции. #1
с самой функцией нет проблем проблема в самой программе задание звучит так
Для заданных двух натуральных числа m и n найти НОД(m, n) и натуральные x и y такие, что mx + ny = НОД(m, n).
программа всё это выполняет но мой цикл просто ужасает и работает очень медленно посмотрите если ес ть идеи подскажите как ускорить работу
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
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
 
 int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
 }
  int qqq(int a, int b,int c)
  {
  double x,y;
   for(x=-10000;x<10000;x++)
      {
   for(y=-10000;y<10000;y++)
 
 
   if((x==(c-y*b)/a)&&(x!=0))
   {
   printf("\nx=%.lf   y=%.lf",x,y);
   return x;
  }
      }
  }
 
 void main(void)
 {
 int n,m;
 int c;
 scanf("%d%d",&n,&m);
 c=gcd(n,m);
 printf("%d",c);
qqq(n,m,c);
  getch();
 }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.04.2011, 23:44     Рекурсивные функции.
Посмотрите здесь:

C++ рекурсивные функции
рекурсивные функции C++
C++ Рекурсивные функции
Рекурсивные функции C++
C++ рекурсивные функции
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.04.2011, 09:00     Рекурсивные функции. #2
A555, А Вы ничего не путаете?
Например m=10, n=15
НОД(m,n)=НОД(10,15)=5
10*x + 15*y = 5
И при этом числа x и y натуральные?
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
15.04.2011, 17:30  [ТС]     Рекурсивные функции. #3
да всё верно x и y натуральные моя программа выдаёт что х=-10000 и y=6667 хотя я задумался и вспомнил что отрицательные числа не являются натуральными хотя вот само задание из методички преследователя 1. Для заданных двух натуральных числа m и n найти НОД(m, n) и натуральные x и y такие, что mx + ny = НОД(m, n).
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
15.04.2011, 17:44     Рекурсивные функции. #4
НОК
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
15.04.2011, 17:46  [ТС]     Рекурсивные функции. #5
спс но мне нужно НОД найти
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
15.04.2011, 22:05     Рекурсивные функции. #6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <sstream>
 
typedef __int64 LL;
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
LL gcd(const LL &a, const LL &b) { return a ? gcd(b%a, a) : b; }
 
int main(){
    //freopen("test.txt", "r", stdin);
 
    LL n, m, x, y;
    cin >> m >> n;
    LL g = gcd(n, m);
    FOR(i,0,10000){
        if ((i * m - g) % n == 0){
            cout << i << "*" << m << "-" << (i * m - g) / n << "*" << n << "=" << g << endl;
            break;
        }
    }
}
Добавлено через 4 минуты
Код
m*x + n*y = gcd(m,n)
m*x - gcd(m,n) = n*y
Следовательно перебираем все множители х и проверяем на делимось n
Код
( m*x - gcd(m,n) ) mod n == 0
Добавлено через 2 минуты
Если посчитаешь асимптотику, то у тебя работает за квадрат - O(n^2) а у меня за линию O(n) поэтому для чисел до 10^6 в секунду вложишься.
Vergil111
31 / 31 / 6
Регистрация: 30.11.2010
Сообщений: 81
15.04.2011, 23:34     Рекурсивные функции. #7
Используй рекурсию=)
Алгоритм очень шустрый, если числа побольше будут просто используй long=)
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
#include <iostream>
 
using namespace std;
int gcd(int, int, int&, int&);
int main()
{
    int arg1, arg2, x, y;
    cout << "\nEnter first argument ";
    cin >> arg1;
    cout << "\nEnter second argument ";
    cin >> arg2;
    cout << "\n" << gcd(arg1, arg2, x, y)
    << "\nx=" << x << "\ny=" << y << endl;
    return 0;
}
int gcd (int a, int b, int & x, int & y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
15.04.2011, 23:57  [ТС]     Рекурсивные функции. #8
объясни плз что твоя прога вообще делает Vergil111 я смотрю НОД правльно вычисляет и х и у вообще не понятно как
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
16.04.2011, 00:39     Рекурсивные функции. #9
A555, это Диофаново уравнение
http://ru.wikipedia.org/wiki/%D0%94%...BD%D0%B8%D0%B5
http://e-maxx.ru/algo/extended_euclid_algorithm - это решение, асимптотика O(log(n)) (точно не помню, но должна быть как у gcd, а у нее log(n))
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
16.04.2011, 00:46  [ТС]     Рекурсивные функции. #10
слушай а подскажи твой код который ты написал работает не правильно и при любых числах х и у одинаковые и принцип здесь какойто 2-ной рекурсивной функции можешь объяснить немного буду оч благодарен
Vergil111
31 / 31 / 6
Регистрация: 30.11.2010
Сообщений: 81
16.04.2011, 00:47     Рекурсивные функции. #11
Ну смотри=) Как только мы доходим до строчки
C++
1
int d = gcd (b%a, a, x1, y1);
начинается рекурсивный вызов нашей функции, пока мы не упремся в условие
C++
1
2
3
4
if (a == 0) {
                x = 0; y = 1;
                return b;
        }
Это так называемая база рекурсии или если по другому, условие выхода из нее.По определению НОД двух чисел, если одно из них есть 0, равен другому числу и именно это мы и прописываем в этом условии и соответственно получаем наши коэффициенты 0 и 1. А затем мы начинаем прогонять все это в обратном порядке
C++
1
2
x = y1 - (b / a) * x1;
        y = x1;
и в итоге получаем окончательные коэффициенты x и y
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
16.04.2011, 00:58  [ТС]     Рекурсивные функции. #12
блин запусти код на компиляторе ты уидишь о чём я х и у вообще е в тему находит а я понять чего то не могу проверь плз и отпишишь плз
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2011, 01:18     Рекурсивные функции.
Еще ссылки по теме:

C++ Рекурсивные и не рекурсивные функции (вычисление суммы всех натуральных чисел от 1 до n)
C++ Рекурсивные функции
Рекурсивные функции C++

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

Или воспользуйтесь поиском по форуму:
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
21.04.2011, 01:18  [ТС]     Рекурсивные функции. #13
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
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
 int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
 }
  int qqq(int a, int b,int c)
  {
  double x,y;
   for(x=-1;x>-10000;x--)
      {
   for(y=1;y<10000;y++)
 
   if((x==(c-y*b)/a)&&(x!=0))
   {
   printf("\nx=%.lf   y=%.lf",x,y);
return x;
  }
      }
 
  }
 
int main()
 {
 int n,m;
 int c;
 scanf("%d%d",&n,&m);
 c=gcd(n,m);
 printf("%d",c);
qqq(n,m,c);
  getch();
  return 0;
 }
Yandex
Объявления
21.04.2011, 01:18     Рекурсивные функции.
Ответ Создать тему
Опции темы

Текущее время: 14:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru