Меню
Что нового?

Ошибка в использовании рекурсии

ConqU

Новичок
Ошибка в использовании рекурсии

возникла следующая проблема, необходимо написать скрипт, который ишет количество пар допустимых решений ($x,$y) уравнения $x*$x+$y*$y<$n при заданной $n
при использовании функции с рекурсией зависает Апач, функция не перестаёт вызывать сама себя,
ниже привожу кусок кода где непосредственно используется эта функция, если кто-то сможет указать на ошибку, буду очень признателен...

Листинг:

PHP: 
  static $x=0;
  static $y=0;
  static $y_max=0;
  static $i=0;
// counting $y_max

 while ($y*$y<$n)
          {
          $y++;
            return $y;
           }
          if ($y*$y>=$n)
             {
                   $y_max=$y;
                                   }
             $y=0;

 //
 // New function - perebor
   
   function func ($x,$y)
     {
             if ($y=$y_max) return $i;
           while ($y*$y+$x*$x<$n)
             {
                     $x++;
                     $i++;
                     return $i;
             }

             $x=0;
             return func($x,$y++);
     }
    
 //
 echo (func($x,$y));
 echo ("$i");
 
Craelfar

Craelfar

Новичок
while ($y*$y+$x*$x<$n) - а собсна это условие обеспечивает выход из цикла при любых значения переменных? Шот меня терзают смутные сомнения.
 

Lews

Новичок
откуда в функции func возьмутся переменные $i и $y_max?..

Смысл конструкции return func($x,$y++); А точней $y++?

Зачем в самом начале куча статических переменных?..

И так, из любопытсва.. зачем вот этот while
PHP: 
           while ($y*$y+$x*$x<$n) 
             { 
                     $x++; 
                     $i++; 
                     return $i; 
             }
-~{}~ 10.03.06 15:00:

ЗЫ
Вместо echo ("$i"); достаточно писать echo $i;
 

ConqU

Новичок
Я наверно зря не описал алгоритм. исправляю ошибку:
1) сначала считаем максимальное значение У, то есть самое большое решение при Х=0, далее записываем его как У_мах, то есть перебираем значения У пока не перестанет выполняться неравенство
2) Теперь вводим функцию, которая делает следующее:
получает значение У=0 и если оно не равно У_мах, начинает прибавлять значения к Х пока будет выполняться неравенство, как только неравенство перестаёт выполняться, Х обнуляется, к значению У прибавляется единица и снова начинается перебор Х пока после очередного цикла значение У не достигнет максимально допустимого, т.е. У_мах , ну а количество вариантов решения записывается в переменную $i;
3) полученная переменная $i и есть количество всех допустимых решений неравенства т.к. осуществлялся перебор для всех Х при любом У удовлетворяющих неравенству.
Теперь отвечу на вопросы:
2Craelfar
1) не понял.. почему? это условие при котором выполняется перебор значений Х для данного У...
2Lews 1) с переменными $i и $y_max понял, их тоже надо объявить в функции.
2) про $y++ это для начала нового перебора со значением У на ед. выше, для чего это я описал выше
3)про статические переменные: впринципе здесь они не нужны, но они нужны в другом месте, можно считать что они не статические, для жтого куска это не важно
3) этот while как бы и есть пребор значений $x.. Или что ты имел ввиду?
4) про з.ы. - учту
 

Lews

Новичок
Автор оригинала: ConqU
1) сначала считаем максимальное значение У, то есть самое большое решение при Х=0, далее записываем его как У_мах, то есть перебираем значения У пока не перестанет выполняться неравенство
Нажмите для раскрытия...
Наверное проще извлечь квадратный корень из $n и округлить вниз?
PHP: 
$n = 497;
$y_max = floor(sqrt($n));

Автор оригинала: ConqU
2) про $y++ это для начала нового перебора со значением У на ед. выше, для чего это я описал выше
Нажмите для раскрытия...
Посмотри в мане разницу между $y++ и ++$y;


Автор оригинала: ConqU
3) этот while как бы и есть пребор значений $x.. Или что ты имел ввиду?
Нажмите для раскрытия...
Я имел ввиду, что на первой же итерации происходит выход из функции - return $i;

Еще: '=' - присвоение, '==' - сравнение

Так же не имеет смысла передавать перемунню $x в функцию, т.к. все равно передается всегда одно и то же значение - 0.

А вобще, перепиши это все заново и обойдись без рекурсии. Получится 3 строчки =)
 

ConqU

Новичок
2Lews Про while так вот я как раз и спрашиваю, почему функция прерывается после первого же цикла =) Тока я думал что проблема в рекурсии... А где ошибка?

Про $x: как это нет смысла? Важно же количество решений, поэтому надо перебирать пары х-у... Потому что на одно значение У приходится несколько значений Х, удовлетворяющих неравенству...
 

Lews

Новичок
Ты все время передаешь в функцию $x=0. Зачем его передавать, когда можно внутри фукнции объявить переменную $x=0 ? =)

Что такое return знаешь?
Кстати, зачем тебе переменная $i?
 
rotoZOOM

rotoZOOM

ACM maniac
ConqU учить PHP и математику срочно.
PHP: 
$y=floor(sqrt($n));
$cnt=0;
while (true){
    $x=floor(sqrt($n-$y*$y));
    $cnt+=2*$x+1;
    $y--;
    if ($y*$y>$n)break;
}
// в cnt лежит ответ
рексурсия тут не нужна
 

ConqU

Новичок
2Lews 1) С return'ом ошибку нашёл, но это как бы не играет роли, разве что оптимизация...;
2) А переменная $i - и есть количество возможных решений;
3)Так почему же у меня функция-то не работает?? =) Всмысле, объясни плз. где логика нарушается... ;
2rotoZOOM
1) про пхп и математику эт понятно, я как раз этим вот и занимаюсь =) ;
2) Чего-то я не пойму как этот код работает.... да и считает он не то, смотри: например для 2 он выдаёт 9, для 4 - 13, хотя должен выдавать 3 и 4 тк неравенсу X*X + Y*Y < N при значениях N = 2 и 4 будут удолетворять пары х-у: для 2: 1) 0-0 2)0-1 3)1-0. Для 4х останутся эти и добавится пара 4)1-1....ты наверно несколько не так алгооритм понял, точнее то, что надо искать;
3)Если можно без рекурсии, это хорошо конечно, спасибо тебе если алгоритм подскажешь, но всё-таки: где у меня ошибки? =);

-~{}~ 12.03.06 19:10:

кстати, можно это действительно сделать без рекурсий, с помощью вложенных циклов :
При N=3 это будте как-то так:
PHP: 
<?
$y=0;
$x=0;
$n=3;
$cnt=0;
$y_max = floor(sqrt($n));
for($x=0;$y=!$y_max;$y++){
   while ($y=!$y_max)
    {
     $x++;
     $cnt++;
     }
  }
  echo ($cnt);
 ?>
Только тут где-то логическая ошибка, цикл вообще не выполняется, сразу выдаёт ноль..... :D (блин...)
 
zerkms

zerkms

TDD infected
Команда форума
PHP: 
$y=ceil(sqrt($n));
$cnt=0;
while ($y--){
    $x=floor(sqrt($n-$y*$y));
    $cnt += $x + 1;
}
$cnt--;
 

ConqU

Новичок
2zerkms Работает! Большое спасибо, только вот как оно работает? =) ты не мог бы алгоритм пояснить, что-то я не нашёл нигде что такое
PHP: 
ceil
.. да и вообще =)
всем остальным тоже спасибо, если кто-нибудь подскажет как это можно было сделать рекурсией, спасибо вдвойне..:D
 

ConqU

Новичок
Вроде разобрался, только оказалось что код не совсем верный =(
2zerkms
Я тут потестил ещё раз, походу где-то всё-же закралась ошибка: для н=5 выдаёт количество решений = 7, хотя их только 6 :
0-0;
0-1;
0-2;
1-0;
1-1;
2-0;

почему так не знаю, если бы 5 тоже считалось бы решением выдавалось бы 8 (ещё 1-2 и 2-1), тестил много раз, для всех остальных чисел всё нормально вроде...

2VBart .. :) как раз после того как ответил здесь я полез именно туда, куда ты дал ссылку..
 

VBart

Новичок
ConqU
Проблема как раз в том, что вариант от zerkms - 1 2 также считает решением.

-~{}~ 13.03.06 01:09:

самый приметивный вариант который только может прийти в голову:
PHP: 
$n=5;
$max=ceil(sqrt($n));
$cnt=0;
for ($y=0; $y<$max; $y++)
{
 for ($x=0; $x<$max; $x++)
 {
  if ($x*$x+$y*$y < $n) $cnt++;
 }
}
echo $cnt;
-~{}~ 13.03.06 01:13:

Можно сделать проще используя математику, но в час ночи у меня так и не вышло верного решения.
 
zerkms

zerkms

TDD infected
Команда форума
согласен, не учёл
PHP: 
$y=ceil(sqrt($n - 0.1));

$cnt=0;
while ($y--){
    $x=floor(sqrt($n-$y*$y));
    if ($x*$x + $y*$y >= $n) {
    	$x--;
    }
    $cnt += $x + 1;
}
$cnt--;
-~{}~ 13.03.06 11:22:

или даже вот так:
PHP: 
$y = ceil(sqrt($n - 0.1));

$cnt = 0;
while ($y--){
    $x=floor(sqrt($n - $y*$y - 0.1));
    $cnt += $x + 1;
}
$cnt--;
 
rotoZOOM

rotoZOOM

ACM maniac
ConqU То ли я не так понял задание, то ли ты не так объяснил. Если надо найти все целые пары (x,y) чтобы удовлетворяло неравенству, то вот решение:
PHP: 
$y=floor(sqrt($n)-0.00001); 
$cnt=0; 
while (true){ 
    $x=floor(sqrt($n-$y*$y)-0.00001); 
    $cnt+=2*$x+1; 
    $y--; 
    if ($y*$y>=$n)break; 
} 
// в cnt лежит ответ
При выявлении ошибок сначала найди действительно ВСЕ пары.
Пример для n==2: (0,0) (0,1) (0,-1) (-1,0) (1,0)
то есть 5 пар, а не 3.
Первое мое решение было для $x*$x+$y*$y<=$n, так что прошу прощения.
 
Войдите или зарегистрируйтесь для ответа.
Сверху