Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Funkcja znajdująca liczby do utworzenia szukanej wartości - problem.

Ostatnio zmodyfikowano 2013-06-11 11:51
Autor Wiadomość
corthell
Temat założony przez niniejszego użytkownika
Funkcja znajdująca liczby do utworzenia szukanej wartości - problem.
» 2013-06-10 23:32:23
Witam.

Piszę program składający się z kilku modułów. Jednym z nich jest funkcja, która po odczytaniu wartości podanej przez użytkownika zacznie analizować tablicę w której będą już podane jakieś wartości i po ich zsumowaniu wyświetli, które jej elementy tworzą wartość równą podanej przez użytkownika.

żeby to lepiej zobrazować podam przykład:

Jest tablica pudelko_zapalek[]. Zawiera liczby (zapałki) np. 3,18,23,55,12,6,12,17,22,2,8 (ogólnie to mogą być dowolne wartości, także wprowadzane przez użytkownika ale wróćmy do przykładu...)

Teraz np. potrzebuje 37 zapałek... I tu zaczyna się właśnie mój problem ponieważ nie mam pojęcia jak skonstruować taki algorytm, który wyszuka te liczby i je doda tworząc szukaną wartość (jeśli nie będzie możliwości to wyświetli stosowną informacje).

Nie proszę o gotowy kod tylko o jakieś nakierowanie (dodam, że bardzo początkujący ze mnie programista) jednak myślę, że można to zrobić stosując podstawowe instrukcje i wyrażenia języka C++ (tu chodzi raczej o problem natury logicznej :)

Pozdrawiam i proszę o pomoc.
P-85363
Mitu
» 2013-06-11 10:27:29
Jeżeli dobrze rozumiem o co Ci chodzi, to masz tutaj problem plecakowy.

Rozwiązanie na szybko, bruteforcem po wszystkich możliwych rozwiązaniach:

C/C++
#include <iostream>

int sum( int mask[] ) //sumuje "bity" w aktualnej masce
{
    int suma = 0;
    for( int i = 0; i <= 11; i++ ) suma += mask[ i ];
   
    return suma;
}
void inc( int mask[] ) //traktuje elementy talbicy(maski) jako bity i dodaje jeden
{
    for( int i = 0; i < 11; i++ ) //zeruje bity dopoki nie trafi na pierwsze zero i zamienia je na 1
    {
        if( mask[ i ] == 0 )
        {
            mask[ i ] = 1;
            break;
        }
        else mask[ i ] = 0;
       
    }
}

int licz( int dane[], int mask[] ) //wymnaza maske przez zestaw danych
{
    int val = 0;
    for( int i = 0; i < 11; i++ )
    {
        val +=( dane[ i ] * mask[ i ] );
    }
    return val; //zwraca suma
}

int main()
{
    int dane[] = { 3, 18, 23, 55, 12, 6, 12, 17, 22, 2, 8 }; // zbior liczb do sumowania
    int mask[ 11 ] = { 0 }; // zmienne pomocniczne
    int opt[ 11 ] = { 0 }; //
    int val, best = 0, //
    szuk = 37; // szukana suma
   
    do
    {
        val = licz( dane, mask ); //zwraca wartosc
        if( val > best && val <= szuk ) //sprawdza czy nowa wartosc jest lepsza od poprzedniej i czy nie jest wieksza od szukanej
        {
            for( int i = 0; i < 11; i++ ) opt[ i ] = mask[ i ]; // przepisuje aktualna maske do opt (najlepszy zestaw)
           
            best = val; //podmienia stara wartosc najlepsza na nowo znaleziona
        }
        inc( mask ); //zwieksza wartosc maski o 1 (binarne dodawanie jakby)
    } while( sum( mask ) < 11 ); //sprawdza ile "bitow" w masce jest zapelnionych, jesli wszystkie to doszlismu do konca
   
    for( int i = 0; i < 11; i++ ) //przelatujemy przez maske najlepszego zestawu
    {
        if( opt[ i ] == 1 ) std::cout << dane[ i ] << " "; //wypisuje zestawy w oparciu o maske opt
       
    }
}

Śpieszę się, więc nie miałem okazji wszystkiego sprawdzić.
P-85369
corthell
Temat założony przez niniejszego użytkownika
» 2013-06-11 11:51:08
Boszz człowieku jak ty to wymyśliłeś? oO Bardziej skomplikowanego rozwiązania chyba nie mogłem sobie wyobrazić :-) Ehh no nic jako "zaawansowany" początkujący zabieram się za analizę... :) Zobaczymy co z tego będzie. Dzięki za " nakierowanie" ;-P

Pozdrawiam.
P-85371
« 1 »
  Strona 1 z 1