//vkontakte.ru/photo5499957_139306626
Предлагаю вам решить эту задачу _используя рекурсию_ (это условие обязательно, озвучено устно). Слабо? хD
Проблемы:
1) Опечатка в типах х,n
2) Школьник должен знать рекурсивную форму алгоритма быстрого возведения в степень (что не так, по опросам школьников)
3) Возведение в степень – не лучший способ обучения рекурсии
4) Формулировка задачи должна быть наподобие "Запишите на языке программирования рекурсивную формулу" с более явным указанием мест рекурсии
Кто найдёт проблемы ещё? 
P.S. Боюсь, численные методы в школе таки не изучают – особенно такой вывод напрашивается глядя на задание =)
P.P.S Спасибо, конечно, Пашке Джиоеву и Михаилу Асташкевичу – задание представляет из себя запись алгоритма быстрого возведения в степень. Не знал =) Это раскрывает глаза на задумку автора и объясняет, чего хотел преподаватель. Но речь не о том.
Задание должно не только НЕ содержать опечаток, но и в данном случае выглядеть в виде "Запишите рекурсивную формулу в коде" (спасибо Олегу Андрееву за предложенную формулировку =)
9 октября 2009 в 20:05
Ну, вообще это у мну юмор такой))
9 октября 2009 в 18:01
Михаил, это тебе только кажется =) Уверяю тебя как программист и педагог =)))
9 октября 2009 в 17:02
Программист не может быть педагогом, ибо он сродни шаману. И тот, и другой совершают непонятные действия, бормочут что-то себе под нос непонятное, и оба не могут объяснить, как это работает, хотя сами все понимают XDD
9 октября 2009 в 17:00
ООо, не думала, что моя задача поднимет на уши столько людей))) Спасибо вам большое)))
И дополнительных сведений она не давала)
Вообще у нашего препода, даже образования нету педагогического))
9 октября 2009 в 16:01
Фуууух, наконец-то ты меня понял =)) Надо мне было сразу код приводить xD Но это раскрывает карты и делает неинтересным чтение темы новичками, эххх =(((
P.S. Комментарии, если и были, то очень невнятные. Я три раза заставлял страдалицу к учителю подходить с уточняющими вопросами… Удалось только "рекурсия" выцепить О_о
9 октября 2009 в 16:00
#33:
Да, действительно, можно было подумать и так, все думают по разному, но тогда задание становится уж очень странным(видимо это и послужило причиной создания этой темы). Но, повторюсь, скорее всего от учителя были какие-то комментарии перед тем как он это задание давал.
9 октября 2009 в 15:04
2,3,4) Про рекурсивную реализацию было озвучено устно (исправил первый пост =) Кстати, в статье на Википедии (я приводил ссылку выше) алгорим быстрого возведения как раз реализован в НЕрекурсивном виде.
4) Согласен, но для этого ученик должен был понять, что в приведённая формула рекурсивна… Как-то следовало указать на это =) Я (и не только =)из-за незнания формулы быстрого возведения посчитал, что оно на if..else, а рекурсию следует использовать для "добивания" возведения в степень в конце:
function pow(x:real;n:integer):real;
begin
n:=n-1;
if n>0 then
pow:=x*pow(x,n)
else
pow:=x;
end;
var
x,res : real;
n:integer;
begin
write('Enter x '); readln(x);
write('Enter n '); readln(n);
if n=0 then res:=1
else if n<0 then res:=1/pow(x,abs(n))
else if n mod 2=0 then res:=pow(x*2,n div 2)
else res:=pow(x,n-1)*x;
writeln ('Result = ', res);
end.
Согласись, это тоже решение задачи с учётом 1) =))) Причём, замечу, рекурсивное =)))))))
Что скажешь так? =)
9 октября 2009 в 15:04
Причём первоначальная интерпретация задания (без устного "рекурсией") выглядела так:
var x,res : real;
n:integer;
begin
write('Enter x '); readln(x);
write('Enter n '); readln(n);
if n=0 then res:=1
else if n<0 then res:=1/pow(x,abs(n))
else if n mod 2=0 then res:=pow(x*2,n div 2)
else res:=pow(x,n-1)*x;
writeln ('Result = ', res);
end.
9 октября 2009 в 15:04
2) Вообще, мысль, что школьник должен был понять, как этот алгоритм работает (с подсказкой "рекурсия") – интересна, но… Это должен быть прирождённый математик, наверное? =)))
9 октября 2009 в 15:00
Итак по пунктам как я это вижу:
1) "Опечатка в типах х,n" – согласен.
2) "Школьник должен знать рекурсивную форму алгоритма быстрого возведения в степень (что не так, по опросам школьников)"
Школьник не должен знать алгоритм быстрого возведения в степень. В задании как раз дается наглядное описание этого алгоритма, и требуется его реализовать. Из этого описания становится понятно как этот алгоритм работает. Но оно ни в каком месте не указывает на необходимость рекурсивной реализации этого алгоритма.
==============
Приведу пример для алгоритма поиска в связном списке:
если в текущем узле значение совпадает с искомым, вернуть этот узел(или его номер), если нет повторить для следующего.
Явно в описании алгоритма присутствует рекурсия. Однако никто так не делает. Все делают что-то вроде:
while( node != NULL)
{
if ( node.value == search)
{
return node;
}
node = node.next;
}
Т.е. реализация алгоритма нерекурсивна.
=============
Можно посмотреть описание нашего алгоритма, и придумать нерекусивную реализацию:
if ( n < 0 )
{
n = -n;
x = 1/x;
}
result = 1.0;
while ( n )
{
if ( n % 2 )
{
result *= x;
}
x *= x;
n = n / 2;
}
Этот код реализует алгоритм описанный в задании, и рекурсии он не использует.
3) См.предыдущий пункт.
4) Да, возможно следовало бы указать можно ли использовать рекурсию или нет. Я не знаю на самом деле всей подоплеки, возможно препод и говорил, что рекурсию использовать не следует. Скорее всего по этому заданию были какие-то комментарии, и разрешалось задавать вопросы. Но с другой стороны, те ученики которые не разбираются в программировании хорошо, могли просто написать как в бумажке:
double pow( double a, int n)
{
if ( n < 0 )
{
return 1/pow(a, -n);
} else if ( n == 0 )
{
return 1;
} else if ( n%2 )
{
return a * pow(a, n – 1);
} else
{
return pow(a*a, n/2);
}
}
и у них бы все заработало =), и была бы им радость =). Прошу топикстартера описать историю, откуда у него это задание взялось.
9 октября 2009 в 13:00
Машка, перефразируя Пашку – почему?!
9 октября 2009 в 12:02
[Наш с Пашкой троллинг удалил... Пашка, перечитай первый пост =) И дальше будешь спорить? О_о ]
8 октября 2009 в 23:03
господи! блиииин…. посмотрев на то, что вы сдесь пишете, у меня на 98% отбилось желание учиться на программиста….
8 октября 2009 в 22:05
выставить условия,что Х больше нуля и оценить показатель как натуральный. Вот,наверное, ибудет истинной задание
8 октября 2009 в 20:00
Возможные причины:
1) Простой алгоритм вычисления степени, понятный даже школьнику. Сортировать пузырьком ведь учат.
2) Скорость работы – для мелких степеней этот алгоритм будет быстрее pow.
3) Точность – у exp+ln большая погрешность.
ЗЫ В конце концов нигде не написано, что это лучший вариант и каждый раз надо заново изобретать велосипед.
8 октября 2009 в 15:00
Пашка, я не говорю – корректный алгоритм или нет – я говорю, корректно ли задание, даже с предлагаемым исправлением? там есть ещё как минимум две проблемы. Видишь их?
8 октября 2009 в 14:00
Константин Смотритель: Если написать, что x – вещественное, а n – целое, то указанный алгоритм будет корректным.
8 октября 2009 в 5:03
Михаил, ты присмотрись к задаче-то =) Задача школьная,да.
Влад, можно и на Яве – давай код =) Сдавать ещё нескоро О_о
8 октября 2009 в 1:02
java не устраивает? а то я Поска-каль, уже лет 10 не трогал….
8 октября 2009 в 1:02
Костя , скажи честно , тебе когда задачу в школе сдавать?
7 октября 2009 в 22:03
Пашка, а что, проблема данного задания _только_ в этой опечатке? Присмотрись _повнимательнее_, не будь снобом =)
Михаил, а какой тогда смысл в рекурсии? Нет уж, если не используем возведение в степень,так и не используем :-р
7 октября 2009 в 21:05
>> А если серъёзно – два тебе, задача не решена =)))))
Ну хорошо, а если вызвать так:
var
b:real;
…
c:=pow(a,trunc(b))*exp(ln(a),frac(b));
Сойдет?)
7 октября 2009 в 21:04
Ну понятно-же, что в задании ошибка/опечатка и имелась в виду именно целая степень. Учитель тоже человек, может ошибиться. И по этому поводу не стоит заводить тему с громким названием "Качество образования в школе". Вот у меня в школе действительно была плохая учительница по информатике, и вполне возможно, что она никогда не слышала про алгоритм быстрого возведения в степень.
7 октября 2009 в 21:03
#8 – не подсказывай)
до этого надо самому дойти)
7 октября 2009 в 21:02
Михаил, ну ты открыл нам глаза =)
А если серъёзно – два тебе, задача не решена =)))))
7 октября 2009 в 21:02
Хороший анекдот)
7 октября 2009 в 21:02
А не напишу я второй способ )Я про рекурсию забыл)
7 октября 2009 в 21:01
Евгений, глядя на твою аватару, я понимаю причину такого способа =)
Анекдот.
Объявление на вокзале:
- Московское время шесть часов. Для военных: стрелки стоят по стойке "смирно"
Итак, ещё раз для тех, кто в танке: необходимо использовать _рекурсию_
7 октября 2009 в 21:01
Ок. Только на паскале
Если n ненатуреальное, то есть формула
exp(ln(a),b);
которая возводит a в степень b.
Алгоритм быстрого возведения в степень используется обычно (по крайней мере в олимпиадной информатике) для того, чтобы возвести в степень по модулю некоторого числа. Код:
function pow(a,b:longint):longint;
begin
if b=0
then pow:=1 else
if b=1
then pow:=a mod p else
if odd(b)
then pow:=(pow((a*a)mod p,b shr 1)*a) mod p
else pow:=pow((a*a)mod p,b shr 1) mod p;
end;
7 октября 2009 в 21:01
P.S. не знаю, как использовать рекурсию при n ненатуральном )
7 октября 2009 в 21:00
Способ первый:
#include <math.h>
#include <stdio.h>
int main( void )
{
double x = 2.0, y = 3.0, z;
z = pow( x, y );
printf( "%.1f to the power of %.1f is %.1f\n", x, y, z );
}
Второй щас напишу
7 октября 2009 в 20:04
Михаил, код – в студию.
P.S. Вообще, возникла идея тех, кто высказывается не по существу и без кода – банить =)
P.P.S Если ты об этом //ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%B... – то степень здесь _Наутральная_, что нам не подходит
7 октября 2009 в 20:03
#6 +1 =)
7 октября 2009 в 20:03
Также обратите внимание на отсутствие необходимости условия проверки чётности – попробуйте-ка сократить формулы математически =)))))
7 октября 2009 в 20:03
Обычный алгоритм быстрого возведения числа в степень. Не так уж и страшно)
7 октября 2009 в 20:00
#5 – неправильно
Внимательнее прочитай задание…
сигнатура функции должна быть:
double pow(int a, double n);
ЗЫ В задании не указано, что делать для положительных нецелых степеней.
7 октября 2009 в 19:05
А в чем проблема то?
double pow( double a, int n)
{
if ( n < 0 )
{
return 1/pow(a, -n);
} else if ( n == 0 )
{
return 1;
} else if ( n%2 )
{
return a * pow(a, n – 1);
} else
{
return pow(a*a, n/2);
}
}
Конечно можно без рекурсии обойтись.
А вобще рекурсивный код выглядит даже проще, чем нерекурсивный.
7 октября 2009 в 19:04
не проблема)
7 октября 2009 в 19:04
Андрей, а код, код-то где?
7 октября 2009 в 19:04
оперативно=)
ладно, на днях найду время подумать, выложу)