Probleme de informatica - enunturi si rezolvari

Se dau n(n+1)/2 numere naturale aranjate intr-un triunghi format din elementele de sub si de pe diagonala unei matrici patratice de ordin n.
Se calculeaza sume pornind din elementul de pe prima linie prin deplasari in vecinii de sub si din dreapta. Gasiti suma maxima care se poate calcula astfel si care sunt valorile din care se obtine suma maxima.
Exemplu:
n=4
2
3 5
6 3 4
5 6 1 4
suma maxima este 17
si se obtine din valorile 2 3 6 6

#include <fstream>
using namespace std;
ifstream fin ("date.in");
ofstream fout ("date.out");

void citire(int &n, int a[100][100])
{
    int i,j;
    fin>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
            fin>>a[i][j];
}

void drum(int n, int a[100][100], int s[100][100], int i, int j)
{
    if(i>1)
    {
        if(s[i][j]-s[i-1][j-1]==a[i][j]) drum (n,a,s,i-1,j-1);
        else drum (n,a,s,i-1,j);
        fout<<a[i][j]<<" ";
    }
    else fout<<a[1][1]<<" ";
}

int main()
{
    int i,j,a[100][100],n,s[100][100],maxx;
    citire(n,a);
    s[1][1]=a[1][1];
    for(i=2;i<=n;i++)
        for(j=1;j<=i;j++)
           if(j==1) s[i][j]=s[i-1][j]+a[i][j];
           else if(j==i) s[i][j]=s[i-1][j-1]+a[i][j];
                else if(s[i-1][j]<s[i-1][j-1]) s[i][j]=a[i][j]+s[i-1][j-1];
                     else s[i][j]=a[i][j]+s[i-1][j];

    maxx=0;
    int mj;
    for(j=1;j<=n;j++) if(s[n][j]>maxx) { maxx=s[n][j]; mj=j;}
    fout<<maxx<<endl;
    drum(n,a,s,n,mj);
    fin.close();
    fout.close();
    return 0;
}

21 nov 2024

Site-ul conține 884 de probleme rezolvate