PHP Flood. Бином Ньютона. Заметки о самообучении программированию

 
+3
 
PHP
Dum docemus, discimus
  
  У тех, кто начал свое знакомство с программированием часто возникают две преграды: трудности с пониманием терминологии, вторая преграда — незнание или непонимание что можно на том или ином языке написать. Первая трудность с учетом множества справочников, руководств и форумов теперь решается довольно быстро.
   А вот отсутствие практических задач влечет за собой  отсутствие
мотивации к изучению языка в целом. Еще есть страх публиковать свои скрипты, понимая, что они далеки от идеала. Страх критики, наверное, следует преодолевать сразу же, так как именно критика — один из двигателей, который ведет к постижению языка и верным решениям. Сегодня написали  плохо, завтра напишем лучше. Можно сравнить программирование с игрой на музыкальных инструментах. Для хорошей игры нужна постоянная практика, поэтому, вероятно, программирование можно смело отнести к искусству.

   На программирование можно смотреть как на шахматы: игроков двое — лень против силы воли, разум — шахматная доска. Наверное, один из верных способов обучения программированию - это постановка самому себе задач. И не очень важно, будет ли у решений этих задач практическая значимость. Для чего мы играем в шахматы? Упражняемся и развлекаемся. Решаем шахматные задачи и композиции тренировки ради.  
  Так можно отнестись и к программированию, чтобы не ждать момента, когда придет в голову идея написать какую-нибудь полезную программу.  
Мне захотелось написать простенький скрипт для формулы Бинома Ньютона, простое разложение.

А именно для этой формулы:

user posted image, где user posted image - биномиальные коэффициенты.
Формула взята из Википедии.

Вот что получилось. Весь код.

Форма ввода:


Целая неотрицательная степень двух переменных (a+b)^n, где а и b - переменные, n - степень:
<p><form action="binom.php" method="get">a<input type="text" name="a">
b<input type="text" name="b">
n<input type="text" name="n">
 <input type="submit" name="submit" value="Binom it">
 </form>
</p>
Максимальное значение переменных 999:


Кода скрипта:


<?php
if (isset($_GET['submit']) && ($n > 0))  {  
/*Переменные выражения*/
$a=substr(($_GET['a']), 0, 3);
 $b=substr(($_GET['b']), 0, 3);
  $n=substr(($_GET['n']), 0, 3);
   $k="0";

/*Результат сложения переменных a и b и возведения в степень n*/

$res2=bcpow($a+$b, $n);
  echo 'Результат сложения и возведения в степень:';
echo "($a + $b )^$n=";  
echo $res2;

    echo ' <strong>Разложение:</strong>';

/*Изменяемое значение переменной n для убывающей степени (k) переменной а в многочлене*/
$n2=$n;
/*Переменная для факториала числа степени n*/
 $n3=$n;

/*Переменная для суммы разложения*/
    $sm=0;

/*Факториал */

function fuct ($zn)
{
   if($zn <= 1) {

   return 1;
  }

   {
        return $zn * fuct($zn - 1);    }
   
}
/*Факториал n*/
 $factn=fuct($n);


/*Вывод первого одночлена. Вне цикла*/
echo bcpow($a, $n);
  echo "+";

while($k<$n) {
++$k;
 $n2=$n-$k;

/*Степень и произведение a и b*/
$res=bcpow($a, $n2)*bcpow($b, $k);


/*Факториал числа k! знаменателя. Вычитаем из n - k в скобках,
вычисляем факториал. Умножаем значение  в скобках на факториал k!
(по формуле биномиальных коэффициентов)*/
$factk=fuct($k);
 $zn=($n - $k);
  $znn=fuct($zn); 
   $znn2=$factk*$znn;

  /*Делим числитель на знаменатель*/  
   
    $chis=$factn/$znn2;
    
/*Умножаем результат степени и произведения a и b на результат вычисления
биномиального коэффициента*/  
   echo $res*$chis;

/*Суммируем результаты*/  
$sm+=$res*$chis;
echo '+';
 $all=$sm + bcpow($a, $n);
   
}
echo ' Сумма разложения: '; 
  echo $all;
}
  else {
echo ' Степень не должна быть отрицательной '; 
}  
?>


Пример работы калькулятора:
 binom.u-gu.ru/index.php

Update:

Как  сказал в комментариях baldina, легче использовать  формулу без факториалов http://e-maxx.ru/algo/binomial_coeff
Поскольку я не знаком с языком С, то не понял сразу синтаксиса.  И, признаюсь, я не сразу понял, как это реализовать,   пришлось поискать код на других языках  для построения треугольника  Паскаля. Код для треугольника нашелся для Java. Если кому-то интересно, вот ветка: http://hashcode.ru/questions/182043/java-т...ля-без-массивов 

Что можно улучшить?
Вероятно, можно сократить количество итераций, если вынести последний член за пределы цикла, т.е. b в степени n и убрать одну итерацию, т.е. n-1. Заодно, вспомнив, что приоритет операций - деления и умножения одинаковый, то можно в вычислении коэффициента первым поставить деление.  Тогда получаем такой код:


<?php
$a=2;
 $b=3;
  $n=4;
   $ck=1;

echo bcpow($a+$b, $n) . "=";
echo bcpow($a, $n) . "+";

for ($k = 1; $k <= $n-1; $k++) {

  $res=bcpow($a, $n-$k)*bcpow($b, $k);

   $ck = $ck/$k($n-$k+1);

echo $res*$ck . "+";
  }

   echo bcpow($b, $n);

?>



Вообще от второй и предпоследней итерации тоже можно попытаться избавиться, так как вспомнив треугольник паскаля, C(1 n) и С (k n) -
2-ой и предпоследний коэффициенты - всегда будут равны значению степени.  

P.S. Честно говоря, не сразу понял формулу. Хотя, похоже, всё не так уж сложно.

Отраженный треугольник Паскаля

Решил дополнить  заметку одним из способов вывода треугольника Паскаля.
Согласно свойству симметрии, которым обладает треугольник, можно вычислять только половину каждой его строки. Вторую часть выводить через массив. Это, наверное, не самый эффективный способ, но все же он есть:

 

<?php

function tre($n) {

   $ck=1;
/*Число коэффициентов в строке треугольника равно показателю степени + 1*/
     $kn=$n+1;
     
/*Проверка на четность. Если кол. коэф. четное, делить на 2*/

if($kn%2==0) {

$kn=$kn/2;
 $i=0;

}

  else
  
  {
/*Иначе прибавить 1 и поделить на 2. Установить переменную i равной 1.
Требуется для того, чтобы избавиться от лишнего числа при отражении*/
$kn+=1;
 $kn=$kn/2;
  $i= 1;
}

for ($k = 1; $k <= $kn-1; $k++) {


   $ck = $ck/$k*($n-$k+1);
   /*Читает значения строки в массив*/
$arr[] = $ck;
/*Вывод первой части*/
echo  "+" . $ck ;


  }
  

/*Степень 1 не считать*/
if ($kn>1) {
  echo $arr[i];
  /*Переворот массива*/
  $arr=array_reverse($arr);
  
   /*Без последней итерации (kn-1)*/

for ($i; $i<= $kn-1; $i++) {
   /*Выводим вторую часть*/
echo  "+" . $arr[$i]  ;
}

}

}

while ($n<=100) {
++$n;
echo tre($n);
/*Здесь переход на новую строку*/
echo "br";
}


?>


Гаврюшин Иван. Август 2014. 
  
Об авторе
dcc0

Array


Дата публикации: 23.07.2014. Просмотров: 498
Комментарии (22)
ava
baldina | 23.07.2014, 13:30 (Отредактирован 23.07.2014 14:32) #
теперь надо сделать следующий шаг: привести программу в порядок
  1. не стоит публиковать код, который выдает предупреждения интерпретатора
  2. использовать html для решения задачи было не обязательно, но взявшись - держись. Html должен быть корректным надо поправить косяки, плюс неплохо бы данные и представление разнести, убрав оформление в стили.
  3. хорошим тоном также считается разделение html и php. Код можно сконцентрировать в начале, а не размазывать по тексту.
  4. функция вычисления факториала определена три(!) раза. Достаточно одной.
  5. есть еще одна проблема, над решением которой стоит подумать: факториал - быстрорастущая функция. Легко добиться переполнения, и ... нет, работа программы не нарушится (слава php), но значение факториала перестанет быть целым. И проверка на равенство не пройдет (или степень перестанет быть положительной).
ava
dcc0 | 23.07.2014, 15:02 (Отредактирован 23.07.2014 16:27) #
baldina, да, спасибо. С количеством функций факториала я переборщил. Поправил, теперь одна функция. Над остальными замечаниями буду думать.  
C 5 пунктом, похоже, 1 вариант: сделать ограничение для вводимых данных.
ava
baldina | 24.07.2014, 14:38 #
да, как вариант
ava
baldina | 24.07.2014, 14:40 #
$all==$res2

вы все еще сравниваете числа с плавающей запятой? см. хотя бы тут
ava
dcc0 | 24.07.2014, 15:43 (Отредактирован 24.07.2014 17:26) #
Спасибо. Прочитал. Тогда проверка вообще не имеет смысла, если я правильно понял. Хотя несколько чисел после запятой ведь можно сравнивать.
Но далее, если в результате NAN...
is_nan — Проверяет, является ли значение "не числом", как написано.
Что в данном случае неприменимо.  
Видимо, is_finite надо использовать. 
ava
baldina | 24.07.2014, 16:33 #
проверка на прямое равенство - нет. когда результат число с точкой, сравнивают с заданной погрешностью.
если при вычислениях произошло переполнение, и сравнивать нечего.
разные подходы, не приводящие к переполнению (для разумных значений), описаны здесь
ava
baldina | 24.07.2014, 16:37 #
кстати, поскольку биномиальные коэффициенты в разложении появляются последовательно, можно не считать их каждый раз заново, а использовать формулу  C(n,k) = C(n-1,k-1) + C(n-1,k), т.е. использовать треугольник Паскаля неявно. Тогда и факториал считать не нужно.
ava
dcc0 | 24.07.2014, 17:12 #
Я так понял в этом случае, нужно строить таблицу.
Интересный материал по ссылке, внимательно почитаю.

Интересно в самом конце:
"Наконец, в некоторых ситуациях оказывается выгодно предпосчитать заранее значения всех факториалов".

ava
baldina | 28.07.2014, 14:29 (Отредактирован 28.07.2014 15:30) #
можно избавиться от возведения в степень:

$x=$a+$b-1; // x в представлении (1+x)^n
$x_k=1; // x^k
for ($k=0; $k <= $n; ++$k) {
  // use x^k
  $x_k *= $x;
}
ava
baldina | 28.07.2014, 14:43 #
что-то типа http://ideone.com/ugwGG4
ava
dcc0 | 29.07.2014, 11:24 #
Наверное, еще можно заменить умножение сложением.
Но кода станет больше. 
ava
baldina | 29.07.2014, 13:10 #
в данном случае повода для иронии нет, т.к. возведение в целую степень "внутри" реализуется умножением (хотя и не прямолинейным, а с использованием декомпозиции на основе x^n = (x^(n/2))^2)
в использованной схеме умножений столько же, сколько в предыдущей - возведений в степень, что, очевидно, намного эффективнее.
также предлагаю ознакомиться со схемой Горнера
ava
dcc0 | 29.07.2014, 14:22 (Отредактирован 29.07.2014 15:30) #
baldina, это не было иронией.  Разложение на простейшие операции облегчает понимание. Я до сих пор не все понимаю касательно бинома, хотя уже 4 дня активно читаю по комбинаторике и близким разделам.

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

За ссылку Спасибо.



Сам треугольник на php:

<?php

$n=0;

function tre ($n) {
   $ck=1;
  echo "1_";

for ($k = 1; $k <= $n-1; $k++) {

   $ck = $ck/$k*($n-$k+1);

echo $ck . "_";
  }

   echo "1";

}

while ($n<=120) {

++$n;
echo tre($n);
echo "br";
}
?>


ava
baldina | 29.07.2014, 14:52 #
можно не считать в случае, если в памяти создается таблица. например, если нужно получать произвольные биномиальные коэф. см. http://ideone.com/gk9GkM
а когда они идут последовательно, экономить просто не на чем
ava
dcc0 | 29.07.2014, 20:49 (Отредактирован 29.07.2014 21:51) #
Мне в какой-то момент подумалось так:
количество коэф. в каждой строке - это n + 1.
Те, которые нужно считать - это n + 1 - 4, так как фактически известны  1-ый, 2-ой,
предпоследний, последний.
Можно проверить четность-нечетность степени, вычислить начиная с 3-его (вернее, со второго, так как 0!=1) до середины и отразить эту часть в обратном порядке.
Хотя smile слишком заморочено получается...
ava
baldina | 30.07.2014, 18:18 (Отредактирован 30.07.2014 19:23) #

(n,k) :=
  0                 if k > n
  1                 if n<1 or k<1
  n                 if k=1
  (n,n-k)           if k > n/2
  (n-1,k-1)+(n-1,k)
ava
dcc0 | 31.07.2014, 20:32 (Отредактирован 01.08.2014 17:23) #
В PHP же есть деление по модулю. В общем, как-то так. Отражение через массив:


<?php

  $n=5;
   $ck=1;
/*Количество коэф. в каждой строке треугольника
Паскаля равно показателю степени + 1 */
     $kn=$n+1;
     
/*Проверяем четность строки. Если показатель степени нечетный,
то количество коэф будет четным, так как kn+1.
Тогда просто делим на два,
и устанавливаем переменную i для второго цикла (отражения)*/
if($kn%2==0) {

$kn=$kn/2;
 $i=0;

}
/*Если n четное, тогда kn+1 - нечетное. Чтобы разделить на два без остатка добавим 1, поэтому kn+1. Делим на два.
Но у нас количество коэф. нечетное,
поэтому когда будем отражать код из массива,
уберем первую итерацию (после того, как перевернем массив),
тогда i=1 - это и убирает лишнее число
в четных степенях при отражении.*/

  else
  
  {

$kn+=1;
 $kn=$kn/2;
  $i= 1;
}

for ($k = 1; $k <= $kn-1; $k++) {


   $ck = $ck/$k*($n-$k+1);
$arr[] = $ck;

echo  "+" . $ck ;


  }

if ($kn>1) {
  echo $arr[i];
  $arr=array_reverse($arr);
  
for ($i; $i<= $kn-1; $i++) {

echo  "+" . $arr[$i]  ;
}

}
?>
ava
baldina | 01.08.2014, 12:13 #
@dcc0, причем тут деление по модулю?! треугольник симметричен.
ava
baldina | 01.08.2014, 12:15 #
а, вижу...
как-то все сложно и запутанно получилось.
ava
dcc0 | 01.08.2014, 16:09 #
baldina, да несколько запутанный код. Сейчас отредактирую, добавлю комментарии.
ava
dcc0 | 01.08.2014, 16:26 #
Прокомментировал. В общем, конечно, это уже не чистые вычисления, так как вторая часть хранится в массиве, но уже не БД для хранения факториалов.
Но все же, собственно вычисления в этом "отраженном треугольнике Паскаля" сократились. 
ava
dcc0 | 01.08.2014, 21:17 (Отредактирован 02.08.2014 15:00) #
cut
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
  baldina   dcc0
advanced
Отправить