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

Wowa

Дата 9.2.2006, 03:33 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Админ
Сообщений: 15017
Регистрация: 14.9.2000
Где: Винград

Репутация: нет
Всего: 290

Задача: Дана функция 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 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 5
Всего: 99

Если

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

)

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

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

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

Присоединённый файл ( Кол-во скачиваний: 31 )

admin.jpg 82,46 Kb

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

Mayk

Дата 9.2.2006, 09:07 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 2
Всего: 134

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)

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

Это сообщение отредактировал(а) Mayk - 9.2.2006, 09:32

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Wowa

Дата 10.2.2006, 08:02 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Админ
Сообщений: 15017
Регистрация: 14.9.2000
Где: Винград

Репутация: нет
Всего: 290

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 5
Всего: 99

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

)

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

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

--------------------

Wowa

Дата 10.2.2006, 18:46 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Админ
Сообщений: 15017
Регистрация: 14.9.2000
Где: Винград

Репутация: нет
Всего: 290

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

Mayk

Дата 10.2.2006, 19:26 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 2
Всего: 134

Цитата(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

Это сообщение отредактировал(а) Mayk - 10.2.2006, 19:34

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

cardinal

Дата 10.2.2006, 21:48 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 5
Всего: 99

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

)

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

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

Бывает...

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

Код


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

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »