Stavění elektrárny v C :) Vyřešeno

[JayCube]

Zdravim, už zase potřebuji poradit s domácím úkolem. Je to trochu složitější, tak radši přikládám zadání:
Zadání úkolu

► Zobrazit spoiler

Úkolem je vytvořit program, který bude optimalizovat stavbu větrných elektráren.

Základem větrné elektrárny je nosný tubus. Ten je příliš velký než aby bylo možné jej dopravit v jednom kuse. Proto je potřeba jej na místě sešroubovat z jednotlivých menších segmentů. Předpokládejme, že máme vyrobené jednotlivé segmenty, které mají připravené příruby. Oba konce segmentu jsou opatřeny přírubami, pro každou přírubu znáte počet šroubů, kterými se stahuje. Pořadí segmentů je pevně dané, sousední segmenty mají pochopitelně příruby kompatibilní (pro stejný počet šroubů).

Při montáži lze sestavovat segmenty libovolně. Není potřeba tubus stavět od základu po jednom segmentu v pořadí 1 - 2 - 3 - 4, naopak, na zemi lze sestavit více segmentů do většího celku a ten umístit na rostoucí tubus, máme dost výkonný jeřáb. Tedy lze například sestavit segmenty 1 - 2, pak samostatně 3 - 4 a sestavené 3 - 4 umístit na sestavené 1 - 2. Omezující je cena, kterou montáž stojí. Protože tubus musí být ideálně kolmý, musíme při montáži neustále kontrolovat přesnost sestavení.

Předpokládejme, že máme dvě sousedící části tubusu: spodní A a na ni navazující horní B. A i B mohou být tvořeny buď jedním segmentem nebo více segmenty, které byly již dříve sestavené. Část A má spodní přírubu s x1 šrouby a horní přírubu s x2 šrouby, část B má spodní přírubu s x2 šrouby (aby šla sestavit s A) a horní přírubu s x3 šrouby. Na sestavení částí A a B potřebujeme utáhnout x2 šroubů a zkontrolovat přesnost sestavení. Utažení šroubů stojí x2, kontrola sestavení stojí x1 * x3 (kontrolujeme každý s každým šroubem).

Program dostane na vstupu parametry segmentů, ze kterých sestavujeme tubus. Zadané jsou počty šroubů v jednotlivých přírubách. Pokud má například tubus 3 segmenty A, B a C, kde segment A má spodní přírubu s x1 šrouby, horní s x2 šrouby, segment B spodní s x2 šrouby a horní s x3 šrouby a segment C spodní s x3 a horní s x4 šrouby, budou na vstupu 4 celá čísla x1 x2 x3 x4.

Výstupem programu bude vypočtená nejnižší možná cena za kterou lze celý tubus sestavit.

Ukázka práce programu:
Zadejte pocty sroubu pro jednotlive priruby:
30 20 25 10
Cena: 545

Program by měl nejprve vypočítat (30*25+20)+(30*10+20) což je 1090 a pak (20*10+25)+(30*10+20) a to je 545. Druhý výsledek je menší, takže ho zobrazí. jenže těch hodnot může být víc než čtyři a já nevím, jak to udělat, aby vyzkoušel všechny možnosti. Neví někdo jak na to?

[Reklama]

[faraon]

Technický dotaz, ty vstupní údaje budou vždy na jednom řádku, nebo na několika?
Jde o to čím bude ten vstup ukončený, jestli znakem \n, tak není problém napsat si vlastní načítání

Pak už si "jen" uděláš pole spojů sousedních dílů, projdeš ho ve všech permutacích, a budeš si pamatovat nejmenší vypočítanou cenu.

[JayCube]

Vstupní údaje budou na jedné řádce. Načítání už mám:

Kód: Vybrat vše

    if( !(srouby = (int *) malloc( velikost * sizeof(int) )) )
    {
        printf("Málo paměti\n");
        return 1;
    }

    while( (ok = scanf( "%d", &srouby[pocet])) != EOF )
    {
        if( ok!=1 || srouby[pocet]<=0 )
        {
            printf("Nespravny vstup.\n");
            return 1;
        }

        pocet++;

        if( pocet==velikost )
        {
            velikost = velikost * 2;
            if( !(srouby = (int *)realloc( srouby, (velikost) * sizeof(int) )) )
            {
                printf("Málo paměti\n");
                return 1;
            }
        }
    }


V poli "srouby" jsou uložené spoje dílů. Problém je vyzkoušet všechny možnosti. Na vstupu může být mnohem víc hodnot a já nevím jak to zapsat, aby to otestovalo všechny varianty.

[faraon]

V podstatě máš na vybranou jen ze dvou možností, buď se do toho pustit elegantně rekurzí, nebo brutálně pomocí vnořených cyklů.

V obou případech to má ale smysl jen do určitého počtu dílů, protože je to klasický problém obchodního cestujícího, navíc zhoršený o to, že se každým krokem některé hodnoty mění. Každopádně už při nějakých dvaceti dílech nemáš šanci dojít k zaručenému výsledku dřív, než ukončíš tuhle školu

Takže by stálo za to zkusit i třetí cestu, problém si nejdřív důkladně logicky rozebrat a zkusit najít nějaký háček.

[JayCube]

Nakonec se mi to povedlo vyřešit. Použil jsem k tomu Matrix chain multiplication (samozřejmě jsem si to musel trochu poupravit):

Kód: Vybrat vše

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>


int vypocet( int *p, int i, int j )
{
    if( i==j ) return 0;

    int k, min=INT_MAX, cena;

    for( k=i; k<j; k++ )
    {
        cena = vypocet( p, i, k ) + vypocet( p, k+1, j ) + p[i-1]*p[j]+p[k];
        if (cena < min) min = cena;
    }

    return min;
}


int main( void )
{
    int *srouby, pocet=0, ok=0, velikost=4;


    printf("Zadejte pocty sroubu pro jednotlive priruby:\n");

    srouby = (int *) malloc( velikost * sizeof(int) );

    while( (ok = scanf( "%d", &srouby[pocet])) != EOF )
    {
        if( ok!=1 || srouby[pocet]<=0 )
        {
            printf("Nespravny vstup.\n");
            return 1;
        }

        pocet++;

        if( pocet==velikost )
        {
            velikost = velikost * 2;
            srouby = (int *)realloc( srouby, (velikost) * sizeof(int) );
        }
    }

    if( pocet<2 )
    {
        printf("Nespravny vstup.\n");
        return 1;
    }


    printf("Cena: %d\n", vypocet( srouby, 1, pocet-1 ));

    return 0;
}


Termín pro odevzdání už zkončil (já to naštěstí stihl), takže už asi nemá smysl se v tom dál hrabat - téma zamykám. Děkuji za pomoc, díky tomuhle fóru mám zápočet.