Для любителей подумать

Когда-то я заикнулся, что могу предоставить некоторые задачки для любителей поломать голову. Приходит много посланий на мыло и решил некоторые из них выложить на форум.

1. Найти алгоритм для наиболее быстого возведения действительного числа в действительную степень, с наибольшей точностью.


2. Сколькими способами заданное натуральное число N можно представить в виде суммы кубов двух чисел т.е N=a³+b³. Рассмотрите общий случай когда N=a^m+b^m.

3. Есть зеркальный лабиринт. Под углом  0<alpha<Pi/2 к первой стенке падает луч света. Требуется написать алгоритм движения луча в лабиринте и доказать, что при не замкнутой структуре лабиринта всегда найдется выход из него.

Продолжение следует....

решение могут приниматься на мыло [email]andrey@skyriver.ru[/email]

Сообщение отредактировано: GrAnd - 26.05.02, 11:38

На счет третьего пункта: если взять две параллельные стенки и перпендикулярно одной из них пустить луч, то тот выйдет лишь через бесконечное время, т.е. никогда не выйдет...

Цитата PropellerMan, 26.05.02, 14:36:57

На счет третьего пункта: если взять две параллельные стенки и перпендикулярно одной из них пустить луч, то тот выйдет лишь через бесконечное время, т.е. никогда не выйдет...

там же написано alpha<pi/2 ...

1. Быстрым для кого? Для человека или компьютера (с сопроцессором). Чем плох всемизвестный вариант exp(b*ln(a)) для a^b ?

2. Сколькими угодно, т.к. можно составить зависимость a = (N-b³)^1/3, которая решаема при любых b.

3. С чего бы это? Неправда! Вот простейший пример (один из примеров). Дана квадратная комната. Срежем углы (чтобы сделать её незамкнутой). Теперь пустим луч на середину одной из стенки под углом 45^o. Я не прав?
Скорее всего, ты ошибся в постановке задачи....

по поводу 2.
надо решать задачу в целых числах, иначе решение очевидно - бесконечность.
а в целых числах, это переборная задача.
единственное, что можно предложить, это метод сокращения перебора.
итак, есть целые положительные a,b,N.
будем обозначать 3rt(q) - кубический корень из q.
будем также считать, что разложения (a,b) и (b,a) - одно и то же разложение.
Итак, очевидно, что в любом разложении a³+b³=N
a<=3rt(N) => (a+b)<3rt(N)
далее
a³+b³=(a+b)(a*a-a*b+b*b)
Значит N делится на (a+b)
вообще-то, как мне кажеться, но доказать я не смог, a+b<=a*a-a*b+b*b.
поэтому запускаем цикл i от 1 до 3rt(N)
{
если (N\%i!=0)continue; (переходим на следующую итерацию цикла).
  цикл a от 1 до i/2.
 {
    b=i-a;
    если (N/i==(a*a-a*b+b*b)увеличиваем кол-во вариантов разложения. ++kol.
 }
}

теперь в kol кол-во вариантов такого разложения.


Если же надо выяснить кол-во вариантов разложения несокльких чисел, то возможно быдет целесообразнее нагененрить сначала массив кубов чисел, потом для каждого числа :
j=0;
while(cub_arr[j]<3rt(N[i])
{
   bb=N-cub_arr[i];
  если bb есть в cub_arr то увеличиваем kol. ++kol[i]
        проверку на наличие bb в cub_arr лучше сделать бинарным поиском.
   ++i;
}
на выходе будем иметь массив количеств вариантов разложений.

тем же способом можно проверить кол-во вариантов разложения на
a^2k+1+b^2k+1
.

Сообщение отредактировано: Demo_S - 26.05.02, 15:25

Цитата GrAnd, 26.05.02, 12:25:17

доказать, что при не замкнутой структуре лабиринта всегда найдется выход из него.

при незамкнутой структуре, я думаю, выход всегда будет,только не факт, что луч его найдет:)))

Цитата 7in, 26.05.02, 18:48:19

1. Быстрым для кого? Для человека или компьютера (с сопроцессором). Чем плох всемизвестный вариант exp(b*ln(a)) для a^b ?

2. Сколькими угодно, т.к. можно составить зависимость a = (N-b³)^1/3, которая решаема при любых b.

3. С чего бы это? Неправда! Вот простейший пример (один из примеров). Дана квадратная комната. Срежем углы (чтобы сделать её незамкнутой). Теперь пустим луч на середину одной из стенки под углом 45^o. Я не прав?
Скорее всего, ты ошибся в постановке задачи....

1. Данный метод довольно плох при получении заданной точности и вычисления малых величин.

2. Дело в том , что не мешало бы и найти все эти варианты. При этом желательно не пользоваться простым методм перебора.

3. Я думал, что не придется объяснять того, что лабиринт есть некоторая ломанная без самопересечений.
;D ;D ;D

Кстати для лабиринтов со структурой правильных многоугольников луч выйдет не всегда. Достаточно подобрать необходимый угол.  ;D ;D ;D

Цитата GrAnd, 27.05.02, 10:33:23

2. Дело в том , что не мешало бы и найти все эти варианты. При этом желательно не пользоваться простым методм перебора.

а каким? сложным методом, или вообще не перебором?
имхо переборная задача....
может для какого-то конкретного N можно на делимости поиграть, но если на каждом так играть, то ввыйдет дольше чем перебором,... хотя еще подумаю:)

Я имел в виду не просто два цикла с перебором от 1 до N (N^1/3).

Первая задача очень просто решается.
a^b, где b- челое положительное - представляем его в виде битовой последовательности
double tmp=a,res=1;

for (int i=1;i<=BitCount(b);i++)
{
if (Bit(b,i)==1) {res*=tmp;} //Bit(b,i)-возвращает значение i-го бита
tmp*=tmp;
}

Цитата GrAnd, 27.05.02, 10:33:23

2. Дело в том , что не мешало бы и найти все эти варианты. При этом желательно не пользоваться простым методм перебора.

2. Что-то я не понял опять.... Вопрос из ряда: сколько корней имеет уравление y=x? Если нужно, чтобы a и b были тоже натуральными, тогда другое дело.

Цитата

Кстати для лабиринтов со структурой правильных многоугольников луч выйдет не всегда. Достаточно подобрать необходимый угол.

Ну вот ты и сам опроверг условие своей задачи....

Конечно, a и b натуральные.
А что касается лабиринта, то здесь я привел небольшую часть решения.