За последние 24 часа нас посетили 18377 программистов и 1637 роботов. Сейчас ищут 1677 программистов ...

Нахождение сумм произведений элементов массива

Тема в разделе "Решения, алгоритмы", создана пользователем sphinks_a, 19 янв 2012.

  1. sphinks_a

    sphinks_a Активный пользователь

    С нами с:
    17 авг 2011
    Сообщения:
    11
    Симпатии:
    0
    Задача:
    В массиве Аn=[A0,A1,A2...An] найти :
    1) количество множителей пар, троек, четверок, н-множителей
    2) сумму произведений пар, троек, четверок... н-множителей
    Усложнение:
    3) найти количество множителей пар, троек, четверок при м-количестве заданных элементов, где м<n
    4) сумму произведений n-множителей с m-количеством заданных элементов.
    Пример:
    А5=[a,b,c,d,e] n=5.
    1)5-терок = 1 = abcde
    4 = 5= abcd, abce,abde,acde, bcde
    3=10=abc,abd,abe,acd,ace,ade,bcd,bce,bde,cde
    2=10=ab,ac,ad,ae,bc,bd,be,cd,ce,de
    2)S5=abcde;
    S4=abcd+abce+abde+acde+bcde
    S3=abc+abd+abe+acd+ace+ade+bcd+bce+bde+cde
    S2=ab+ac+ad+ae+bc+bd+be+cd+ce+de
    Усложнение: заданные элементы b,d. Тогда:
    1)5-терок = 1 = abcde
    4 = 3= abcd,abde, bcde
    3=3=abd,bcd,bde
    2=1=bd
    2)S5=abcde;
    S4=abcd+abde+bcde
    S3=abd+bcd+bde
    S2=bd
    Итак, приступаем к решению:
    Для начала найдем количество м-элементов в н-массиве с к-заданным количеством элементов. Используем рекурсию и факториал.
    Код (Text):
    1. function factorial($x){
    2.      if($x==0){
    3.       return 1;
    4.      }else{
    5.       return $x*factorial($x-1);
    6.      }
    7.     }
    И создаем ф-цию нахождения м-элементов н-массива с к-заданным кол-вом элементов
    Код (Text):
    1.     function calculate($n,$k){
    2.      for($i=$n;$i>$k;$i--){
    3.                     $columns[$i]=factorial($n-$k)/(factorial($i-$k)*factorial($n-$i));
    4.             }
    5.             return $columns;
    6.     }
    Решение не очень красивое, но поэтому и нужна помощь. Тут чувствую тоже рекурсия должна быть, может кто подскажет.
    Итак, ф-ция возвращает массив, номер элемента которого соответствует количеству м-элементво, а значение элемента - количеству соединений м-элементов.
    Т.е. при n=5, к=0 columns=[5=>1, 4=>5, 3=>10, 2=>10, 1=>5].
    А при n=5, к=2 columns=[5=>1, 4=>3, 3=>3, 2=>1]. Единицы опускаются, т.к. условие - минимум 2 элемента.
    Дальше- больше.
    Нужно найти сумму произведений. И вот тут вопрос: КАК????
    Чувствую, рекурсия нужна. Т.к. без рекурсии вообще труба получается. Вот ф-ция нахождения для n=5
    Тут $arg2- массив с 5-ю элементами, а $arg1-что именно мы ищем(пары, тройки и т.д)
    Код (Text):
    1.  
    2.     function getSum($arg1,$arg2){
    3.      switch($arg1){
    4.       case 5: break;
    5.       case 4: break;
    6.       case 3: break;
    7.       case 2: for($i=0;$i<count($arg2);$i++){
    8.                     for($j=$i+1;$j<count($arg2);$j++){
    9.                        $sum2+=$arg2[$i]*$arg2[$j];
    10.                    }
    11.                  }
    12.        return $sum2;
    13.        break;
    14.       default: return 0;
    15.      }
    16.     }
    Из примера видно, что с каждым $arg1+1 будет увеличиваться вложение for(). Поэтому это не решение, а издевательство какое-то.!!!
    Может кто-то уже встречался с подобным? ПОмогите разобраться.
     
  2. yuri

    yuri Активный пользователь

    С нами с:
    16 янв 2012
    Сообщения:
    288
    Симпатии:
    2
    Контрольная по информатике? :)
     
  3. sphinks_a

    sphinks_a Активный пользователь

    С нами с:
    17 авг 2011
    Сообщения:
    11
    Симпатии:
    0
    Нет. Для практического применения.
    Кстати, решение уже нашел.
    Если кому интересно, могу выложить.
    Если нет - тему фтопку!
     
  4. Gromo

    Gromo Активный пользователь

    С нами с:
    24 май 2010
    Сообщения:
    2.786
    Симпатии:
    2
    Адрес:
    Ташкент
    sphinks_a
    выкладывай решение, раз уж нашёл. иначе публикация в этом разеделе не имеет смысла :)
     
  5. sphinks_a

    sphinks_a Активный пользователь

    С нами с:
    17 авг 2011
    Сообщения:
    11
    Симпатии:
    0
    Итак:
    Решение рекурсией
    Код (Text):
    1.    
    2.     //наш массив с a,b,c,d...n значениями
    3.     $mas=[a,b,c,d];
    4.      
    5.   //создаем вспомогательный массив
    6.     for($i=0;$i<count($mas)+1;$i++){
    7.         $a[$i]=0;
    8.     }
    9.      
    10.     function get_mult($last_idx,$product,$num_el,$mas,$a){
    11.                     //values_games;
    12.                     $this->a[$num_el]+=$product;
    13.                     while(++$last_idx<count($mas)){
    14.                             $s=$product*$mas[$last_idx];
    15.                             $this->get_mult($last_idx,$s,$num_el+1,$mas,$this->a);
    16.                     }
    17.             }
    18.     //вызов ф-ции
    19.     $this->get_mult(-1,1,0,$mas,$this->a);
    20.      

    на выходе имеем массив а[], в котором индекс массива соответствует соединениям (пара-тройка-четверка), а значение - сумме произведений.
    Если есть фиксированные значения, отделяем фиксированные значения и не фиксированные. Фиксированные перемножаем между собой, а в ф-цию передаем массив с не фиксированными значениями. И на выходе массив а перемножаем с произведением фиксированных значений.