[es] - Provera da li se rec moze sastaviti od niza slova

Radovan__III
Radovan__III
Beograd

Član broj: 15669
Poruke: 1245
79.101.209.*

+26 Profil

Provera da li se rec moze sastaviti od niza slova

^{24.02.2009. u 10:09 - pre 184 meseci}

Deluje jednostavno ...

Imam niz reci i niz slova

$a=array("marko","mirko","marina","petar");
$b=array("a","m","r","i","n","k","o");

Treba mi metoda ( ili funkcija ) koja prima niz reci i niz slova i proverava da li je moguce sastaviti rec od datih slova (ps: rec marina nije moguce sastaviti jer nisu ponudjena dva slova "a".
Trebalo bi da se vrati nesto tipa : "Moguce je sastaviti reci marko i mirko"

Aj sad svi u biblioteku da nesto pojedemo i popijemo ...
--------------------------------
Knjigovodstvo

jablan

Član broj: 8286
Poruke: 4541

+711 Profil

Re: Provera da li se rec moze sastaviti od niza slova

^{24.02.2009. u 10:55 - pre 184 meseci}

Evo ti u rubiju, ako ti nije problem da prevedeš u PHP...

Code:

def nadji_sve reci, slova
  ssj = slova.sort.join
  reci.find_all do |rec|
    rec.split('').sort.join.scan(/((.)\2*)/).map{|m| m[0]}.all?{|ss| ssj.include?(ss)}
  end
end

Primer:

>> nadji_sve ['ana', 'banana', 'na'], ['n', 'n']
=> []
>> nadji_sve ['ana', 'banana', 'na'], ['a', 'n']
=> ["na"]
>> nadji_sve ['ana', 'banana', 'na'], ['a', 'n', 'a']
=> ["ana", "na"]
>> nadji_sve ['ana', 'banana', 'na'], ['a', 'n', 'a', 'a']
=> ["ana", "na"]
>> nadji_sve ['ana', 'banana', 'na'], ['a', 'n', 'a', 'a', 'b']
=> ["ana", "na"]
>> nadji_sve ['ana', 'banana', 'na'], ['a', 'n', 'a', 'a', 'b', 'n']
=> ["ana", "banana", "na"]

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

Član broj: 54774
Poruke: 876
*.teol.net.

+148 Profil

Re: Provera da li se rec moze sastaviti od niza slova

^{24.02.2009. u 13:17 - pre 184 meseci}

Evo i brute force rjesenje, otkucao sam nabrzinu i nisam detaljno provjeravao:

Code:

<?php

    $imena = array("marko","mirko","marina","petar");
    $slova = array("a","m","r","i","n","k","o");

function napraviRijec($rijec,$slova) {
    for ($i=0; $i<strlen($rijec); $i++) {
        $match = false;
        for ($j=0; $j<count($slova); $j++)
            if ($rijec[$i] == $slova[$j])
                $match = true;
        if (!$match)
            return false;
        }
    return true;
    }


function moguceRijeci($imena, $slova) {
    $j=0;
    for ($i=0; $i<count($imena); $i++)
        if (napraviRijec($imena[$i],$slova)) {
            $res[$j++] = $imena[$i];
            }
    return $res;
    }

$rjesenje = moguceRijeci($imena,$slova);
print_r($rjesenje);
?>

Tudfa
Jovicevic Vladimir

Član broj: 152699
Poruke: 384
*.dynamic.sbb.rs.

+3 Profil

Re: Provera da li se rec moze sastaviti od niza slova

^{24.02.2009. u 13:17 - pre 184 meseci}

EDIT: Pretece me Ivan

Evo i u Php-u nesto sto bi trebalo da bude to sto si zeleo :

Code:

$words   = array("marko","mirko","marina","petar");
$letters = array("a","m","r","i","n","k","o");

function find_word($word,$letters)
{
    for($i=0;$i<strlen($word);$i++)//svako slovo u datoj reci
    {
        for($j=0;$j<count($letters);$j++)//uporedjujemo sa svakim od zadatih slova
        {
            if($word[$i] === $letters[$j])//ako je trazeno slovo pronadjeno
            {
                $letters[$j] = '';//to slovo vise ne mozemo koristiti
                break;//a zatim prelazimo na sledece slovo u datoj reci
            }
        }
        if($j == count($letters)){return false;}//vraca se false, u slucaju da trazenog slova nema
    }
    return true;//vraca se true ako je svako potrebno slovo pronadjeno
}

I onda samo tu funkciju pozivas ovako :

Code:

foreach($words as $word)
{
    if(find_word($word,$letters))
    {
        echo 'Nadjeno : '.$word.'<br>';
    }
}

Dobices izlaz :

Code:

Nadjeno : marko
Nadjeno : mirko

Pa sad ti mozes da doradis/prepravis kod kako ti odgovara, ali ovo je neka logika kojom bi mogao to da resis.

poz

Nikola Poša
Backend (PHP) developer
Beograd

Član broj: 173839
Poruke: 1616
147.91.216.*

+33 Profil

Re: Provera da li se rec moze sastaviti od niza slova

^{24.02.2009. u 13:36 - pre 184 meseci}

A evo i moje varijante, ovako na prvu loptu...

Code:

<?php
function provera($niz_imena, $niz_slova) {
    $niz_rezultat = array(); //u njega ce se upisati rezultat ove f-je
    $temp_niz_slova = $niz_slova; //privremeni niz koji ce se koristiti za uporedjivanje

    //... i krecemo... :)
    foreach ($niz_imena as $imena) {
        for ($i = 0; $i < strlen($imena); $i++) {
            if (in_array($imena{$i}, $temp_niz_slova)) {
                if ($i == strlen($imena) - 1) { //ako se stiglo do poslednjeg slova imena, shto znachi da su pronadjena sva slova iz imena
                    $niz_rezultat[] = $imena;
                }
                unset($temp_niz_slova[array_search($imena{$i}, $temp_niz_slova)]); //izbacivanje onog slovnog kraktera za koji se pronashlo poklapanje
            }
            else {
                break;
            }
        }
        $temp_niz_slova = $niz_slova; //resetovanje privremenog niza
    }

    return $niz_rezultat;
}

Code:

//Primer
$a = array("marko", "mirko", "marina", "petar");
$b = array("a", "m", "r", "i", "n", "k", "o");

$niz = provera($a, $b);
if(!empty($niz)) {
print_r($niz);
}
else {
echo 'Nema podudaranja.';
}
?>

Output bi trebao da izgleda ovako: Array ( [0] => marko [1] => mirko ), shto je u tom sluchaju tachno...

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

Član broj: 54774
Poruke: 876
*.teol.net.

+148 Profil

Re: Provera da li se rec moze sastaviti od niza slova

^{24.02.2009. u 14:53 - pre 184 meseci}

Hehe, forum je ziv, kako su svi pozurili da daju rjesenja. :)

Btw, sada sam vidio da moj kod bas i ne radi to sto bi trebalo, tj. ne uzima u obzir da se svako slovo moze iskoristiti samo jednom, ali kako su ponudjena i ostala rjesenja, nema potrebe da ga sada prepravljam.

Poz

Shomybg88
Student

Član broj: 267288
Poruke: 7
*.adsl-a-1.sezampro.rs.

+1 Profil

Re: Provera da li se rec moze sastaviti od niza slova

^{10.03.2012. u 21:36 - pre 147 meseci}

Pozdrav

Da li bi neko mogao ko zna pascal da mi napise slican kod u pascalu.
Jedino sto reci ne treba da budu u nizu nego u txt fajlu (svaka rec u zasebnom redu)
I sad unose se slova i program treba da od tih slova izabere najduzu rec iz fajla i ispise je na standardnom izlazu.
Nesto slicno ako ste gledali muzicku slagalicu pa igra koja se zove bas 'slagalica'. Sastaviti najduzu rec od ponudjenih slova. Samo sto slova ne treba random da budu, nego ih ja unosim.
Pretpostavimo da postoji fajl u kome su sve moguce reci odvojene enterom (novim redom).

Hvala unapred pozz
Moze i neki drugi programski jezik, ali paskal jedino znam da pokrenem, nisam vest u ostalima:-)