Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Jeden na wiesz i kolumne

0 views
Skip to first unread message

Matuzalem

unread,
Jan 23, 2010, 1:45:53 PM1/23/10
to
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

Wit Jakuczun

unread,
Jan 23, 2010, 2:02:40 PM1/23/10
to
On 23 Sty, 19:45, Matuzalem <codemast...@op.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

Matuzalem

unread,
Jan 23, 2010, 2:23:11 PM1/23/10
to
On 23 Sty, 20:02, Wit Jakuczun <wit.jakuc...@gmail.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

Mariusz Marszałkowski

unread,
Jan 23, 2010, 2:35:28 PM1/23/10
to
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

Matuzalem

unread,
Jan 23, 2010, 2:45:43 PM1/23/10
to
On 23 Sty, 20:35, Mariusz Marszałkowski <mmars...@gmail.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

Jędrzej Dudkiewicz

unread,
Jan 23, 2010, 4:28:08 PM1/23/10
to
Matuzalem pisze:

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

JD

Wit Jakuczun

unread,
Jan 23, 2010, 4:49:32 PM1/23/10
to
On 23 Sty, 20:23, Matuzalem <codemast...@op.pl> wrote:
> On 23 Sty, 20:02, Wit Jakuczun <wit.jakuc...@gmail.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_hetman%C3%B3w

Na dole masz opis wersji dla wież.

Pozdrawiam,
Wit Jakuczun

Mariusz Marszałkowski

unread,
Jan 23, 2010, 5:10:19 PM1/23/10
to
On 23 Sty, 22:28, Jędrzej Dudkiewicz <jedrzej.dudkiew...@gmail.com>
wrote:
No wlasnie, ale nie wiemy czy mozna wstawic jednynke w miejsce
zera, czy tylko zero w miejsce jedynki :)
Pozdrawiam

Matuzalem

unread,
Jan 23, 2010, 9:00:51 PM1/23/10
to
On 23 Sty, 23:10, Mariusz Marszałkowski <mmars...@gmail.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

0 new messages