Премини към съдържанието

Препоръчан отговор


Здравейте,

Имам задача за домашно с рекурсия и алгоритъм раделяй и владей. Мисля че проблемът е, че не мога да си представя как да се реши задачата с рекурсия и разделянето. Уловието е да се напише програма която решава умножение на две квадратни матрици с размер 2^n използвайки divide and coquer и recursion. Как да започна измислянето на функцията и разделянето на матрицата на подматрици? Как да започна да мисля рекурсивно?

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Първа стъпка е да решиш задачата без рекурсия.

Рекурсията не  нищо повече от функция която извиква себе си. Не бих казал че е даже начин на мислене пък да не говорим че рядко се използват и не са препоръчителни.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Как се умножават квадратни матрици съм забравил. И това там 2 на ента степен ли е ?

За рекурсията не съм съгласен. Как така ще е безсмислена, като се явява използване на служебния стек ? Като е толкова безсмислено да се използва логиката на стека, защо тогава създателите на STL са се потрудили да напишат темплейта stack ?

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
преди 1 час, Zealar написа:

Първа стъпка е да решиш задачата без рекурсия.

Рекурсията не  нищо повече от функция която извиква себе си. Не бих казал че е даже начин на мислене пък да не говорим че рядко се използват и не са препоръчителни.

Аз си я реших задачата на листче и с for цикли, но с рекурсия нищо не ми идва в главата.

Току що, Реджеп Иведик написа:

Как се умножават квадратни матрици съм забравил. И това там 2 на ента степен ли е ?

За рекурсията не съм съгласен. Как така ще е безсмислена, като се явява използване на служебния стек ? Като е толкова безсмислено да се използва логиката на стека, защо тогава създателите на STL са се потрудили да напишат темплейта stack ?

Квадратна матрица - |2 3| * |2 3|  = a11 = 2*2 + 3 * 1; a12 = 2*3 + 3*1 ...
                                     |1 3|   |1 1|
                                     

Редактирано от frozener (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Ако не се сеща какво това divide and coquer и recursion търси алгоритъм на Щрасен за бързо умножение на матрици.


  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
преди 51 минути, ined написа:

Ако не се сеща какво това divide and coquer и recursion търси алгоритъм на Щрасен за бързо умножение на матрици.

Divid and conquer четох, че е да разделям проблема на малки подпроблеми докато може да се реши проблема с една операция.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Нали това е идеята да се научиш. Става доста по-лесно когато имаш нещо на екрана от колкото да се пробваш да измислиш всичко наум.

Затова решаваш задачата по тривиалният начин, след това слагаш принт да покаже всяка операция и хоп , програмата ти написва следващата.

Ето бърз пример за матриците.

#include<iostream>
#include<string>
using namespace std;

void printResult(int (&arr)[2][2], int size, string txt)
{
    cout<< txt << endl;
    for(int j=0; j<size;j++)
    {
        cout<<"| ";
        for(int i=0; i<size;i++)
        {
            cout<<arr[j][i]<<" | ";
        }
        cout <<endl;
    }
}

int main(){
    const int SIZE = 2;
    int A[SIZE][SIZE] = {{2,3},{1,3}};
    int B[SIZE][SIZE] = {{2,3},{1,1}};
    int C[SIZE][SIZE];
    for(int row=0; row<SIZE;row++)
    {
        for(int col=0; col<SIZE;col++)
        {
            C[row][col]=0;
            for(int i=0;i<SIZE;i++)
            {
                C[row][col]+=A[row][i]*B[i][col];
                cout << "$C [" << row << "]" << "[" << col << "] += "
                << "$A [" << row << "]" << "[" << i << "] (" << A[row][i] << ") "
                << " * "
                << "$B [" << i << "]" << "[" << col << "] (" << B[i][col] << ") "
                << endl;
            }
        }
    }
    printResult(A, SIZE, "Matrica A : ");
    printResult(B, SIZE, "Matrica B : ");
    printResult(C, SIZE, "Resultat : ");
    return 0;
}

Решена без рекурсия но както се забелязва има принт за стъпките, от което получавам следният изход.

Цитат
$C [0][0] += $A [0][0] (2)  * $B [0][0] (2)                                                                                                                                                                                      
$C [0][0] += $A [0][1] (3)  * $B [1][0] (1)                                                                                                                                                                                      
$C [0][1] += $A [0][0] (2)  * $B [0][1] (3)                                                                                                                                                                                      
$C [0][1] += $A [0][1] (3)  * $B [1][1] (1)                                                                                                                                                                                      
$C [1][0] += $A [1][0] (1)  * $B [0][0] (2)                                                                                                                                                                                      
$C [1][0] += $A [1][1] (3)  * $B [1][0] (1)                                                                                                                                                                                      
$C [1][1] += $A [1][0] (1)  * $B [0][1] (3)                                                                                                                                                                                      
$C [1][1] += $A [1][1] (3)  * $B [1][1] (1)  

Следващата стъпка е просто да проследиш модела и по него да конструираш рекурсията.

Както е всеизвестно рекурсията извиква самата себе си докато не стигне до резултат.

Следователно трябва да имаш стойност която се променя и при определени условия да върне резултат.

От горният изход се забелязва кое се сменя (т.е индексите) и при какви условия връщат резултат (тук зависи в кой ред ще въртиш цикала).

 

Може и текущият начин за пресмятане да го превърнеш в рекурсия и после да оптимизираш стъпка по стъпка.

 

#include<iostream>
#include<string>
#define SIZE 2
using namespace std;
    int A[SIZE][SIZE] = {{2,3},{1,3}};
    int B[SIZE][SIZE] = {{2,3},{1,1}};
    static int C[SIZE][SIZE];
    
void printResult(int (&arr)[SIZE][SIZE], string txt)
{
    cout<< txt << endl;
    for(int j=0; j<SIZE;j++)
    {
        cout<<"| ";
        for(int i=0; i<SIZE;i++)
        {
            cout<<arr[j][i]<<" | ";
        }
        cout <<endl;
    }
}
void recursive(int row, int col, int index)
{
    if (row < SIZE)
    {
        if (col < SIZE)
        {
            if (index < SIZE)
            {
                C[row][col]+=A[row][index]*B[index][col];
                cout << "$C [" << row << "]" << "[" << col << "] += "
                << "$A [" << row << "]" << "[" << index << "] (" << A[row][index] << ") "
                << " * "
                << "$B [" << index << "]" << "[" << col << "] (" << B[index][col] << ") "
                << endl;
                recursive(row, col, index+1);
                return;
            }
            else
            {
                recursive(row, col+1, 0);
                return;
            }
        }
        else
        {
           recursive(row+1, 0, 0);
           return;
        }
    }
}
int main(){

    recursive(0, 0, 0);
    // for(int row=0; row<SIZE;row++)
    // {
    //     for(int col=0; col<SIZE;col++)
    //     {
    //         C[row][col]=0;
    //         for(int i=0;i<SIZE;i++)
    //         {
    //             C[row][col]+=A[row][i]*B[i][col];
    //             cout << "$C [" << row << "]" << "[" << col << "] += "
    //             << "$A [" << row << "]" << "[" << i << "] (" << A[row][i] << ") "
    //             << " * "
    //             << "$B [" << i << "]" << "[" << col << "] (" << B[i][col] << ") "
    //             << endl;
    //         }
    //     }
    // }
    printResult(A, "Matrica A : ");
    printResult(B, "Matrica B : ");
    printResult(C, "Resultat : ");
    return 0;
}

 

Редактирано от Zealar
Добавен пример (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
преди 1 час, Zealar написа:

Нали това е идеята да се научиш. Става доста по-лесно когато имаш нещо на екрана от колкото да се пробваш да измислиш всичко наум.

 

Ще се пробвам сам да я реша и тогава ще сверя с твоето решение. Мисля да направя функция, която да връща умножението на елементите от матрицата, но не знам как да променям индексите при рекурсивното извикване.

Редактирано от frozener (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Не се бъркай, това което съм показал не е решение а по-скоро съвкупност от идеи който да те ориентират. Относно индексите виж в кода който съм показал.

Там само съм заменил циклите с рекурсия.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
преди 21 часа, Zealar написа:

Не се бъркай, това което съм показал не е решение а по-скоро съвкупност от идеи който да те ориентират. Относно индексите виж в кода който съм показал.

Там само съм заменил циклите с рекурсия.

Прочетох алгоритма чрез разделяй и владей и твоята идея не следва този алгоритъм. При разделяй и владей трябва масива да се разделя на подматрици от по един елемент(в различни квадранти) и да се умножават подматриците и вкарват в нова матрица, а за събирането не знам.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Виж условието на темата "Как да мисля рекурсивно" не е "Някой да ми реши задачата".

Показах как да решиш задачата без рекурсия като стъпка първа при такива проблеми.

След това същото решение да го превърнеш в рекурсивно (да видиш как се използва викане на същият метод с други индекси).

Остана само да приложиш изисквания алгоритъм а ми казваш " твоята идея не следва този алгоритъм. " :ohmy:

И един ред код не си показал даже.

#include <iostream>
#define SIZE 2
using namespace std;

void printArray(int arr[SIZE][SIZE], std::string txt)
{
    cout << txt << endl;
    for (int j = 0; j < SIZE; j++)
    {
        cout << "| ";
        for (int i = 0; i < SIZE; i++)
        {
            cout << arr[j][i] << " | ";
        }
        cout << endl;
    }
}
void recursive(int a[SIZE][SIZE], int b[SIZE][SIZE], int c[SIZE][SIZE])
{
    static int sum, i = 0, j = 0, k = 0;
    if (i < SIZE)
    {
        if (j < SIZE)
        {
            if (k < SIZE)
            {
                sum = sum + a[i][k] * b[k][j];
                k++;
                recursive(a, b, c);
                return;
            }

            c[i][j] = sum;
            sum = 0;
            k = 0;
            j++;
            recursive(a, b, c);
            return;
        }
        j = 0;
        i++;
        recursive(a, b, c);
    }
}
int main()
{

    int A[SIZE][SIZE] = { { 2, 3 }, { 1, 3 } };
    int B[SIZE][SIZE] = { { 2, 3 }, { 1, 1 } };
    int C[SIZE][SIZE];
    recursive(A, B, C);

    printArray(A, "Matrica A : ");
    printArray(B, "Matrica B : ");
    printArray(C, "Resultat : ");
    return 0;
}

 

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
публикувано (редактирано)
преди 36 минути, Zealar написа:

Виж условието на темата "Как да мисля рекурсивно" не е "Някой да ми реши задачата".

 Я, интересна дискусия. :) Ако искаш наистина да си помогнеш с рекурсивното мислене, разкарай статичните променливи от функцията. И това дето го казаха горе, че рекурсията не е начин на мислене, не е правилно. Баш начин на мислене и адресиране на проблем е. Всяка рекурсия е аналогична на  един или няколко цикъла и контейнери за съхраняване на временния резултат. Всъщност точно това прави и компилатора, като за контейнер използва стека на процеса. Тоест от теб зависи, какво решение ще избереш - дали да си направиш явно съхранението на временните данни или да оставиш езика да го направи вместо теб. Ако си разбрал достатъчно добре конкретния алгоритъм (забележи - не рекурсията ) - примерно в случая, как се умножават матрици чрез подматрици, останалото е лесно.

П.П. и се отучи да кръщаваш функции "recursive" - много е вредно, честно.

П.П.2 Това че рекурсии не се препоръчват е вярно отчасти и само за някои езици - (вкл. C вариантите обаче)  Има рекурсии, които нативно и елементарно се превръщат в цикли - т.нар. tail recursion. Има езици, които са направо базирани на рекурсия, та чак нямат друг вид цикли.  Толкоз относно начина на мислене :) Ако знаеш, колко навътре ще влезе рекурсията в твоята програма, няма лошо да я ползваш и в C.

Редактирано от flare (преглед на промените)
  • Харесва ми 2

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
преди 7 минути, flare написа:

 ....

П.П.2 Това че рекурсии не се препоръчват е вярно отчасти и само за някои езици - (вкл. C вариантие обаче)  Има рекурсии които нативно и елементарно се превръщат в цикли - т.нар. tail recursion. Има езици които са направо базирани на рекурсия, та чак нямат друг вид цикли.  Толкоз относно начина на мислене :) Ако знаеш колко навътре ще влезе рекурсията в твоята програма, няма лошо да я ползваш и в C.

примерно forth :) (писал съм на него)

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
Току що, capnemo написа:

примерно forth :) (писал съм на него)

Или моя любим Haskell :D

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
публикувано (редактирано)
преди 2 часа, Zealar написа:

Виж условието на темата "Как да мисля рекурсивно" не е "Някой да ми реши задачата".

Показах как да решиш задачата без рекурсия като стъпка първа при такива проблеми.

След това същото решение да го превърнеш в рекурсивно (да видиш как се използва викане на същият метод с други индекси).

Остана само да приложиш изисквания алгоритъм а ми казваш " твоята идея не следва този алгоритъм. " :ohmy:

И един ред код не си показал даже.

 

 

Няма абсолютно никакъв смисъл от подобна менте рекурсия.

Рекурсивното решение на задачата е разделянето на матрицата и 4 по-малки, тях на 4 още по-малки докато не стигне до матрица 1х1.

Затова и метода е "разделяй и владей" или "divide et impera" както са казвали римляните.

   

Редактирано от ined (преглед на промените)
  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

А как се разделя матрица ?

И каква връзка има произведението от предходната стъпка на рекурсията с произведението от следващата ?

Как после да се обединят разделените матрици, и хем да има полза от предходната стъпка ?

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
публикувано (редактирано)
Цитат

Как после да се обединят разделените матрици, и хем да има полза от предходната стъпка ?

Ако ги обединява по формулите за матрица 2х2 няма полза - имаш 8 умножения и 4 събирания, а степента на сложност на умножението е O(n^3) - но това, че не е по-бързо не значи, че няма да работи и може да го използва за решаване на задачата. По алгоритъма на Щрасен с няколко допълнителни събирания и изваждания намалява броя на умноженията на 7 и степента на сложност пада до O(n^2.81)

 

Редактирано от ined (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
публикувано (редактирано)
преди 13 минути, ined написа:

Ако ги обединява по формулите за матрица 2х2 няма полза - имаш 8 умножения и 4 събирания, а степента на сложност на умножението е O(n^3) - но това, че не е по-бързо не значи, че няма да работи и може да го използва за решаване на задачата. По алгоритъма на Шрасен с няколко допълнителни събирания и изваждания намалява броя на умноженията на 7 и степента на сложност пада до O(n^2.81)

За големи матрици има полза. Освен това разсъжденията ви са в контекста на конкретната задача, не по принцип, какъвто е въпроса. Ако се ползва паралелизация например, или библиотека с готови функции (примерно работещи на видеокарта), или се ползва divide and conquer за друго, в зависимост от конкретната среда, може да е много по-бързо.

Редактирано от flare (преглед на промените)
  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
публикувано (редактирано)

Определено многото шейдърни процесори във видеокартите от висок клас вършат много добра работа в случая. Съмнявам се обаче автора да може да подкара някоя CUDA или OpenCL библотека щом още не е написъл задачата и за х86 процесор

 

Редактирано от ined (преглед на промените)
  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
публикувано (редактирано)
преди 12 минути, ined написа:

Определено многото шейдърни процесори във видеокартите от висок клас вършат много добра работа в случая. Съмнявам се обаче автора да може да подкара някоя CUDA или OpenCL библотека щом още не е написъл задачата и за х86 процесор

Не е толкова важно, какво може сега, всичко се учи. Пък и едно не е голяма философия, две може да не му е това работата - примерно в по-голям проект, на него може да му възложат да разбие определена задача на по-малки и да вика код написан от някой друг.  Важното е идеята зад конкретното нещо. Аз затова гледам да не задълбавам в конкретната задача, ами обръщам внимание на това, което има значение.

Редактирано от flare (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 8
int temp[N/2][N];

void print(int m[][N])
{
     int i,j;
     printf("\n\n");
     for (i=0;i<N;++i)
     {
         for (j=0;j<N;++j)
             printf("%8d ",m[i][j]);
         printf("\n\n");
     }
     printf("\n");
}

void add(int *m,int *t,int n)
{
    int i,j,*p,*q;
    
    for (i=0; i<n; ++i)
    {
       p=m+i*N;
       q=t+i*N;
       for (j=0; j<n; ++j)
          *(p++)+=*(q++);
    }
}

void mul(int *c,int *a, int *b, int n)
{
     int h=n/2; 
     int *c2, *c3, *c4;
     int *a2, *a3, *a4;
     int *b2, *b3, *b4;
     int *t=(int*)temp+N-n;
     if (n==1) *c=(*a)*(*b);
     else
     {
          /*   | c c2|   | a a2|   | b b2|        
               |c3 c4|   |a3 a4|   |b3 b4|    */
         
         
         a2 = a + h; a3 = a + h*N; a4 = a3 + h;
         b2 = b + h; b3 = b + h*N; b4 = b3 + h;
         c2 = c + h; c3 = c + h*N; c4 = c3 + h;
         
         mul( c, a, b,h); mul(t,a2,b3,h); add( c,t,h);
         mul(c2, a,b2,h); mul(t,a2,b4,h); add(c2,t,h);
         mul(c3,a3, b,h); mul(t,a4,b3,h); add(c3,t,h);
         mul(c4,a3,b2,h); mul(t,a4,b4,h); add(c4,t,h);   
     }
}

int main()
{
    int i,j,k,t;
    int A[N][N], B[N][N], C[N][N];
    srand(time(NULL));
    for (i=0; i<N; ++i)
        for (j=0; j<N; ++j)
        {
            A[i][j]=rand()%100;
            B[i][j]=rand()%100;;
        }
    printf("Matrix A");  print(A);
    printf("Matrix B");  print(B);
    printf("Matrix C Recursive Calculation");  
    mul((int*)C,(int*)A,(int*)B,N); print(C);
    
    printf("Matrix C Iterative Calculation");  
    for(i=0; i<N; ++i)
       for(j=0; j<N; ++j)
       {
          t=0; 
          for(k=0; k<N; ++k)
              t+=A[i][k]*B[k][j];
          C[i][j]=t;
       }
    print(C);
}

 

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

×

Информация

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