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

Рекурсия. Найти решения неравенства (x^2+ y^2 <= n) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
24.09.2011, 16:14     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n) #1
Новый учебный год, а задачки старые)
Ребят, помогите рекурсивно решить задачку. Классическими - структурными алгоритмами (без излишеств, буст и т.д.)
Без рекурсии можно решить через 2 вложенных цикла, а как рекурентно хз..


Задание:
Напишите программу, печатающую количество натуральных решений неравенства
x^2+ y^2 <= n для введенного натурального числа n.

Направьте на правильный путь.

Добавлено через 27 минут
к примеру, решение этой задачи прямым перебором. Вложенный цикл, последовательно увеличение по условию.
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 <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
 
int main(int argc, char *argv[])
{
 
double n,res,x,y;
cin >> n;
double count_res = 0;
for(x =1; x < n; x++)
  for(y=1; y<n; y++)
  
  {
        res = pow(x,2) + pow(y,2);
           count_res++;
           
           if (n >= res) 
           { 
           
                 cout << x << "  " << y << "   " << endl;
           count_res++; 
           
           }
  };
            cout << "Result: " << count_res << endl;
 
    system("PAUSE");
    return EXIT_SUCCESS;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
24.09.2011, 16:30     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n) #2
Каждый из циклов можно представить в виде рекурсивной функции (а можно и оба цикла представить в виде одной функции, если ввести дополнительный параметр-флаг):
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
#include <stdio.h>
#include <stdlib.h>
 
#ifndef NDEBUG
#define PRINT(X, Y) printf(#X " = %u, " #Y " = %u\n", X, Y)
#else
#define PRINT(X, Y) ((void) 0)
#endif
 
size_t solve(size_t);
 
int main()
{
    size_t n, cnt;
    
    do
    {
    puts("Input n: ");
    scanf("%u", &n);
    }
    while(n == 0);
    
    printf("Calculating for n = %u\n", n);
 
    cnt = solve(n);
    printf("Number of solutions: %u\n", cnt);
    
    exit(0);
}
 
size_t solve_on_y(size_t x, size_t y, size_t n)
{
    if(y >= n)
    return 0;
 
    if(x * x + y * y <= n)
    {
    PRINT(x, y);
    return 1 + solve_on_y(x, y + 1, n);
    }
    else
    return solve_on_y(x, y + 1, n);
}
 
 
size_t solve_on_x(size_t x, size_t n)
{
    if(x >= n)
    return 0;
 
    return solve_on_y(x, 1, n) + solve_on_x(x + 1, n);
}
 
size_t solve(size_t n)
{
    return solve_on_x(1, n);
}
KuKu
 Аватар для KuKu
1538 / 1016 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
24.09.2011, 16:31     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n) #3
Идешь из нуля по спиральке, пока x или y по модулю меньше или равны корню из n и считаешь решения, которые удовлетворяют неравенству. Это извращение, но работать должно)
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
25.09.2011, 11:39  [ТС]     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n) #4
Цитата Сообщение от KuKu Посмотреть сообщение
Идешь из нуля по спиральке
протопал, что дальше?
вы действительно думаете что помогли этими словами?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.09.2011, 11:45     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n) #5
А еще можно сгенерировать сразу все возможные решения, и удалить из них те, которые не удовлетворяют неравенству. Только реализовывать это на Си будет крайне неудобно и неэффективно. Да и вообще на любом не-ленивом языке
KuKu
 Аватар для KuKu
1538 / 1016 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
25.09.2011, 11:46     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n) #6
Цитата Сообщение от IIIa66uMEM6eP Посмотреть сообщение
протопал, что дальше?
вы действительно думаете что помогли этими словами?
Попробуйте прочитать все предложение.
З.Ы. Слова после запятой это тоже часть предложения.
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
25.09.2011, 21:27  [ТС]     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n) #7
Ребят, есть ли паскалисты? перевожу данную прогу на паскаль.ABC выдает ошибку, ошибка переполнение стека , вылетает после выполнения 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
program dad;
function solve_on_y(x,y,n:real):real;
begin
 if y >= n then
  solve_on_y:=0;
 if (x*x+y*y) <= n then
  begin
   writeln(x,' ',y);
   solve_on_y:=solve_on_y(x,y+1,n)+1;
  end
 else
  solve_on_y:=solve_on_y(x,y+1,n);
end;
 
function solve_on_x(x,n:real):real;
begin
 if x >= n then
  solve_on_x:=0;
 solve_on_x:=solve_on_y(x,1,n)+solve_on_x(x+1,n);
end;
 
function solve(n:real):real;
begin
 solve:=solve_on_x(1, n);
end;
 
var
  n,cnt:real;
begin
 repeat
  write('Input n : ');
  readln(n);
 until n<>0;
 writeln('Calculating for n = ',n);
 cnt := solve(n);
 writeln('Number of solutions: ',cnt);
end.
Миниатюры
Рекурсия. Найти решения неравенства (x^2+ y^2 <= n)  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.09.2011, 21:53     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n)
Еще ссылки по теме:

C++ Рекурсия: найти произведение чисел от A до B
Рекурсия. Найти многократно вложенный корень C++
C++ Рекурсия. Найти произведение ряда

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

Или воспользуйтесь поиском по форуму:
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
25.09.2011, 21:53  [ТС]     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n) #8
Решил прогу, более не востребовано.
Yandex
Объявления
25.09.2011, 21:53     Рекурсия. Найти решения неравенства (x^2+ y^2 <= n)
Ответ Создать тему
Опции темы

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