Witam

Mam oto taka macierz:

| 1 0 1 0 |
| 0 0 0 1 |
| 1 1 0 0 |
| 0 0 1 1 |

Jest ona zapisana jako:

typedef std::vector<int> mxrow;
typedef std::vector<mxrow> matrix;

Co nalezy wykonac, aby koncowa macierz wygladala nastepujaco:

| 1 0 0 0 |
| 0 0 0 1 |
| 0 1 0 0 |
| 0 0 1 0 |

Czyli, jak widac w kazdym wierszu i w kazdej kolumniej jest tylko
jedna jedynka

Dzieki
Pozdrawiam

do góry

On 23 Sty, 19:45, Matuzalem <c...@o...pl> wrote:

> Mam oto taka macierz:
>
> |   1   0   1   0   |
> |   0   0   0   1   |
> |   1   1   0   0   |
> |   0   0   1   1   |
>
[..]
> Co nalezy wykonac, aby koncowa macierz wygladala nastepujaco:
>
> |   1   0   0   0   |
> |   0   0   0   1   |
> |   0   1   0   0   |
> |   0   0   1   0   |
>
> Czyli, jak widac w kazdym wierszu i w kazdej kolumniej jest tylko
> jedna jedynka
>
Należy usunąć zbędne jedynki.

Pozdrawiam,
Wit Jakuczun

do góry

On 23 Sty, 20:02, Wit Jakuczun <w...@g...com> wrote:
> Należy usunąć zbędne jedynki.
>
> Pozdrawiam,
>    Wit Jakuczun
Gdyby to bylo takie proste, nie pisalbym tu :)

Jak je usunac ? nie chodzi mi o implementacje tylko algorytm.
Np. usowanie pierwszej lepszej jedynki i zerowanie kolejnych nie daje
oczekiwanych wynikow, jak rowniez, zapamietywanie wiersza/kolumny
gdzie juz usunieto jedynke. Sprawdzanie kazdego wiersza i kolumny
konkretnego elementu nie dziala w kazdej sytuacji.

Pozdrawiam

do góry

On 23 Sty, 20:23, Matuzalem <c...@o...pl> wrote:
> On 23 Sty, 20:02, Wit Jakuczun <w...@g...com> wrote:> Należy usunąć
zbędne jedynki.
>
> > Pozdrawiam,
> >    Wit Jakuczun
>
> Gdyby to bylo takie proste, nie pisalbym tu :)
>
> Jak je usunac ? nie chodzi mi o implementacje tylko algorytm.
> Np. usowanie pierwszej lepszej jedynki i zerowanie kolejnych nie daje
> oczekiwanych wynikow, jak rowniez, zapamietywanie wiersza/kolumny
> gdzie juz usunieto jedynke. Sprawdzanie kazdego wiersza i kolumny
> konkretnego elementu nie dziala w kazdej sytuacji.
>
Jak to nie działa?
Zliczam jedynki, usuwam o jedną mniej niż naliczylem i musi zostać
jedna, no
chyba żeby było z początku mniej niż jedna jedynka :)
Pozdrawiam

do góry

On 23 Sty, 20:35, Mariusz Marszałkowski <m...@g...com> wrote:
> Jak to nie działa?
> Zliczam jedynki, usuwam o jedną mniej niż naliczylem i musi zostać
> jedna, no
> chyba żeby było z początku mniej niż jedna jedynka :)
> Pozdrawiam
Wpadlem na taki pomysl i wyglada na to , ze dziala :)
1. Szukam wiersza/kolumny gdzie jest tylko jedna jedynka
2. zeruje wszystkie inne pozycje tam gdzie zostala znaleziona
3. wracam do punktu 1

a jesli np. nie ma nigdzie wiersza/kolumny z jedna jedynka wybieram
losowy wiersz/kolumne i zostawiam tylko jedna jedynek reszte zeruje :]

Jak narazie dziala na kazdym przykladzie :D

Dzieki
Pozdrawiam

do góry

Matuzalem pisze:
> On 23 Sty, 20:35, Mariusz Marszałkowski <m...@g...com> wrote:
>> Jak to nie działa?
>> Zliczam jedynki, usuwam o jedną mniej niż naliczylem i musi zostać
>> jedna, no
>> chyba żeby było z początku mniej niż jedna jedynka :)
>> Pozdrawiam
> Wpadlem na taki pomysl i wyglada na to , ze dziala :)
> 1. Szukam wiersza/kolumny gdzie jest tylko jedna jedynka
> 2. zeruje wszystkie inne pozycje tam gdzie zostala znaleziona
> 3. wracam do punktu 1
>
> a jesli np. nie ma nigdzie wiersza/kolumny z jedna jedynka wybieram
> losowy wiersz/kolumne i zostawiam tylko jedna jedynek reszte zeruje :]

Z tego co rozumiem, to najlepiej wyzerować wszystko i wstawiać w n-tym
wierszu w n-tej kolumnie.

JD

do góry

On 23 Sty, 20:23, Matuzalem <c...@o...pl> wrote:
> On 23 Sty, 20:02, Wit Jakuczun <w...@g...com> wrote:> Należy usunąć
zbędne jedynki.
>
> > Pozdrawiam,
> >    Wit Jakuczun
>
> Gdyby to bylo takie proste, nie pisalbym tu :)
>
> Jak je usunac ? nie chodzi mi o implementacje tylko algorytm.
http://pl.wikipedia.org/wiki/Problem_o%C5%9Bmiu_hetm
an%C3%B3w

Na dole masz opis wersji dla wież.

Pozdrawiam,
Wit Jakuczun

do góry

On 23 Sty, 22:28, Jędrzej Dudkiewicz <j...@g...com>
wrote:
> Matuzalem pisze:
>
> > On 23 Sty, 20:35, Mariusz Marszałkowski <m...@g...com> wrote:
> >> Jak to nie działa?
> >> Zliczam jedynki, usuwam o jedną mniej niż naliczylem i musi zostać
> >> jedna, no
> >> chyba żeby było z początku mniej niż jedna jedynka :)
> >> Pozdrawiam
> > Wpadlem na taki pomysl i wyglada na to , ze dziala :)
> > 1. Szukam wiersza/kolumny gdzie jest tylko jedna jedynka
> > 2. zeruje wszystkie inne pozycje tam gdzie zostala znaleziona
> > 3. wracam do punktu 1
>
> > a jesli np. nie ma nigdzie wiersza/kolumny z jedna jedynka wybieram
> > losowy wiersz/kolumne i zostawiam tylko jedna jedynek reszte zeruje :]
>
> Z tego co rozumiem, to najlepiej wyzerować wszystko i wstawiać w n-tym
> wierszu w n-tej kolumnie.
>
No wlasnie, ale nie wiemy czy mozna wstawic jednynke w miejsce
zera, czy tylko zero w miejsce jedynki :)
Pozdrawiam

do góry

On 23 Sty, 23:10, Mariusz Marszałkowski <m...@g...com> wrote:
> No wlasnie, ale nie wiemy czy mozna wstawic jednynke w miejsce
> zera, czy tylko zero w miejsce jedynki :)
> Pozdrawiam

Te wartosci ktore sa juz zerami takowymi pozostaja, na tomiast mozna
'zaglowac' jedynkami, ale w taki sposob aby w kazdym wierszu i w
kazdej kolumnie byla tylko jedna jedynka w linii prostej.

Sposob jaki wymyslilem... dziala :)

Pozdrawiam

do góry