Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Анализ алгоритма. Не тупым, а умным способом :)

Автор: Wowa 9.2.2006, 03:33

Задача: Дана функция rev(m,n). Нужно найти все возможные целочисленные значания m,n, при которых: rev(m,n) не зацикливалась бы.

Код


int rev(int m,int n)
{
while ((m<-30) || (n<-30) || (m>20) || (n>20)) { System.out.Println(1); }
While (m>0) { m=m-10;}
while (n*m != 14 ) { System.out.Println(1); }
return (1);
}

Как бы вы решили эту задачу? В голове просчитали бы все возможные варианты? На это минут 5 бы ушло точно я думаю. Что много.
Есть вариант проще, чтобы вычислить m и n ? Без помощи компьютера.

Тут около 10 пар m, n, передав которые в функцию не происходит ее зацикливания.

Автор: cardinal 9.2.2006, 04:10

Если

Цитата(Wowa @ 9.2.2006, 01:33

)

Без помощи компьютера.

то вот так бы решал я...

А что это будет wenn es fertig ist? (нем.: когда будет готово)

Автор: Mayk 9.2.2006, 09:07

14 можно разложить на 8 пар: (1,14), (2,7), (-1,-14), (-2,-7) (14,1), (7,2), (-14,-1), (-7,-2)
Пусть первый множитель обозначает n, второй m.

Так как после преобразований m < 0, то остаётся четыре пары (-1,-14),(-2,-7), (-14,-1), (-7,-2).

Пусть n=-1. Единственный возможный вариант m = -14. (-1,-14).
Пусть n=-2. Тогда m=-7+10i. (i>=0) m=-7, 3, 13 +3 пары
Пусть n=-14. Тогда m=-1+10i (i>=0) m=-1, 9,19 +3 папы
Пусть n=-7, тогда m=-2+10i (i>=0) m=-2,8,18 +3 пары.

Итого 10 пар:
(m,n) := (-1,-14) | (-2,-7) | (-2, 3) | (-2, 13) | (-14, -1) | (-14, 9) | (-14, 19) | (-7, -2) | (-7, 8) | (-7, 18)

зы. разумеется я проверил, перед постингом сюда =)

Автор: Wowa 10.2.2006, 08:02

Цитата(cardinal @ 9.2.2006, 02:10

)

то вот так бы решал я...

У меня тоже вышло 4 пары, а нужно 10 smile

Цитата(Mayk @ 9.2.2006, 07:07

)

Итого 10 пар:
(m,n) := (-1,-14) | (-2,-7) | (-2, 3) | (-2, 13) | (-14, -1) | (-14, 9) | (-14, 19) | (-7, -2) | (-7, 8) | (-7, 18)

вроде правильно.
Добавлено @ 08:06
Вот эти вот не дают ведь 14 в произведении:
(-2, 3) | (-2, 13)
(-14, 9) | (-14, 19)
(-7, 8) | (-7, 18)

Автор: cardinal 10.2.2006, 17:12

Цитата(Wowa @ 10.2.2006, 06:02

)

Вот эти вот не дают ведь 14 в произведении

Не дают, поэтому происходит зацикливание...

Автор: Wowa 10.2.2006, 18:46

угу, но решений больше должно быть.

Автор: Mayk 10.2.2006, 19:26

Цитата(Wowa @ 10.2.2006, 12:02

)

Вот эти вот не дают ведь 14 в произведении:
(-2, 3) | (-2, 13)
(-14, 9) | (-14, 19)
(-7, 8) | (-7, 18)

Цитата(Mayk @ 9.2.2006, 13:07

)

Пусть первый множитель обозначает n, второй m.

Цитата(Wowa @ 9.2.2006, 07:33

)

Код Java
int rev(int m,int n)
{
while ((m<-30) || (n<-30) || (m>20) || (n>20)) { System.out.Println(1); }
While (m>0) { m=m-10;}
while (n*m != 14 ) { System.out.Println(1); }
return (1);
}

(-2,3) -> rev(m=3,n=-2)

while( (3<-30) || (-2 < -30) || (3 > 20) || (-2 > 20) ) не-выполняется;;;
While (3>0) { m=3-10;} //m=-7
While (-7>0) не-выполняется;;;
while(-2 * -7 != 14)не-выполняется;;;;

-2 на -7 даёт 14.
Ну что я делаю не так smile

Добавлено @ 19:32

Код


int rev(int m,int n)
{
 while ((m<-30) || (n<-30) || (m>20) || (n>20)) return 0;
 while (m>0) { m=m-10;}
 while (n*m != 14 ) return 0;
 return (1);
}

int main()
{
        for(int m=-30;m<=20;++m)
                for(int n=-30;n<=20;++n)
                        if(rev(m,n))
                                printf("(%d,%d)\n",n,m);

}

Цитата

(-1,-14)
(-2,-7)
(-7,-2)
(-14,-1)
(-2,3)
(-7,8)
(-14,9)
(-2,13)
(-7,18)
(-14,19)

Ну что гнус делает не так? smile

Автор: cardinal 10.2.2006, 21:48

Цитата(Mayk @ 10.2.2006, 17:26

)

Ну что я делаю не так

Все ты делаешь так! Я только теперь допер в каком месте я тормозил. smile

Бывает...

Я более менее проигнорировал строку

Код


While (m>0) { m=m-10;}