☰

» »

Uganka!!

Uganka!!

Lucifix ::

Zdej pa ena uganka oz. bolj logična stvar. Imam eno slikco:. Zdej pa iščem "genija", ki bi mi znal ta lik potegnt z eno črto (brez prekinjanja). Jst se že kr neki cajta mučm!

Thomas ::

Iz 4 kvadratov z diagonalo je. Treba je narisat enega za drugim.

:)
Man muss immer generalisieren - Carl Jacobi

Lucifix ::

Ja ampak pol bi šel po isti črti? To pa ne smeš.

Thomas ::

Niti slučajno!

Premisli nekoliko, no. Najprej naredi pravilno en kvadratek z diagonalo. Naprej je simpl. :)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Bluzu sem ... sam nimam zdej časa se naprej s tem ukvarjat. Apologize. Tonight. :)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Bom prašal AI. Sam jo moram (to komponento) še narest nocoj.

:)
Man muss immer generalisieren - Carl Jacobi

blabla ::

A connected graph has an Eulerian trail iff it has at most two vertices of odd degree.

Torej naj to ne bi bilo mogoče. Se mi zdi :D

Lucifix ::

Mah jst sem po mojem skor vse kombinacije probu, pa zmeri ena črtica zmanka. Že dolg nazaj mi je ratal, sam tko da sem list papirja prepognu na pol in je nekak ratal. Sam ne vem če je to edina rešitev?!

Brane2 ::

Tko na prvi uč ni videt, da bi se to dal. Namreč na vsakem stičišču daljic, razen v centru imaš liho število daljic.

Kar pomeni, da ti nujno ena zmanjka. Če N <> 2X za celoštevilčni X, potem nimaš zadosti poti, da bi stišče zapustil, potem ko X-tič prideš vanj...

Res je, da lahko najprej narediš pot po zunanjem kvadratu in s tem zreduciraš nalogo na njegovo notranjost, a s tem v bistvu nič ne spremeniš. V stičiščih še vedno ostane liho število poti...

Thomas ::

Ni rešitve.

;)
Man muss immer generalisieren - Carl Jacobi

freejack ::

Hmm,..men tut vedno zmanjka ena črtica. Pa sploh obstaja rešitev?

Thomas ::

Ne obstaja. Napisal sem program, ki je to preveril.

:)
Man muss immer generalisieren - Carl Jacobi

.:joco:. ::

Pri takih zadevah se preveri križišča. Ta deliš z dve in zadevo zaokrožiš navzgor. S tolikimi potezami se to da narisat.

Vsaj mislim da je tako. Vem da je ena čist izy fora.
"Is science true?"
You don't get it.
Science is the process of trying to find out what's true.

Popcek ::

blabla: A connected graph has an Eulerian trail iff it has at most two vertices of odd degree. .

Eulerjev sprehod: je sprehod, kjer se vsaka povezava grafa uporabi natano 1X... graf pa ga ima, ko sta kvečjemu dve toči lihe stopnje(še ti dve sta krajišči)
ta graf ma pa kar 4 toče lihe stopnje -->
grafa se ne da narista z eno potezo.....
:| diskretne FRI .... to mi deli:D

Thomas ::

Problem, za splošni graf, če ima Hamiltonovo pot, je v načelu NP.

"Moj" program, ki je preveril neeksistenco take poti za tale graf je:






    #COMPILE EXE




    Function Main () As Long


    ti=timer

    Dim s(8)

    s(0)="Sever"
    S(1)="Jug"
    S(2)="Vzhod"
    S(3)="Zahod"
    s(4)="SZ"
    s(5)="SV"
    s(6)="JZ"
    s(7)="JV"
    s(8)="Center"

    Dim pot( 23)

    pot(00)="04"
    pot(01)="05"
    pot(02)="14"
    pot(03)="15"
    pot(04)="45"
    pot(05)="46"
    pot(06)="48"
    pot(07)="57"
    pot(08)="58"
    pot(09)="67"
    pot(10)="68"
    pot(11)="78"
    pot(12)="04"
    pot(13)="05"
    pot(14)="14"
    pot(15)="15"
    pot(16)="45"
    pot(17)="46"
    pot(18)="48"
    pot(19)="57"
    pot(20)="58"
    pot(21)="67"
    pot(22)="68"
    pot(23)="78"


    h=space(14)
    For x00=0 to 23
    mid(h,1,1)=chr(65+x00 mod 14)
    For x01=0 to 23
    If Asc(pot(x00),2)=Asc(pot(x01),1) Then
    mid(h,2,1)=chr(65+x01 mod 14)
    If InStr(h,chr(65+x01 mod 14))<2 Then iterate
    For x02=0 to 23
    If Asc(pot(x01),2)=Asc(pot(x02),1) Then
    mid(h,3,1)=chr(65+x02 mod 14)
    If InStr(h,chr(65+x02 mod 14))<3 Then iterate
    For x03=0 to 23
    If Asc(pot(x02),2)=Asc(pot(x03),1) Then
    mid(h,4,1)=chr(65+x03 mod 14)
    If InStr(h,chr(65+x03 mod 14))<4 Then iterate
    For x04=0 to 23
    If Asc(pot(x03),2)=Asc(pot(x04),1) Then
    mid(h,5,1)=chr(65+x04 mod 14)
    If InStr(h,chr(65+x04 mod 14))<5 Then iterate
    For x05=0 to 23
    If Asc(pot(x04),2)=Asc(pot(x05),1) Then
    mid(h,6,1)=chr(65+x05 mod 14)
    If InStr(h,chr(65+x05 mod 14))<6 Then iterate
    For x06=0 to 23
    If Asc(pot(x05),2)=Asc(pot(x06),1) Then
    mid(h,7,1)=chr(65+x06 mod 14)
    If InStr(h,chr(65+x06 mod 14))<7 Then iterate
    For x07=0 to 23
    If Asc(pot(x06),2)=Asc(pot(x07),1) Then
    mid(h,8,1)=chr(65+x07 mod 14)
    If InStr(h,chr(65+x07 mod 14))<8 Then iterate
    For x08=0 to 23
    If Asc(pot(x07),2)=Asc(pot(x08),1) Then
    mid(h,9,1)=chr(65+x08 mod 14)
    If InStr(h,chr(65+x08 mod 14))<9 Then iterate
    For x09=0 to 23
    If Asc(pot(x08),2)=Asc(pot(x09),1) Then
    mid(h,10,1)=chr(65+x09 mod 14)
    If InStr(h,chr(65+x09 mod 14))<10 Then iterate
    For x10=0 to 23
    If Asc(pot(x09),2)=Asc(pot(x10),1) Then
    mid(h,11,1)=chr(65+x10 mod 14)
    If InStr(h,chr(65+x10 mod 14))<11 Then iterate
    For x11=0 to 23
    If Asc(pot(x10),2)=Asc(pot(x11),1) Then
    mid(h,12,1)=chr(65+x11 mod 14)
    If InStr(h,chr(65+x11 mod 14))<12 Then iterate
    For x12=0 to 23
    If Asc(pot(x11),2)=Asc(pot(x12),1) Then
    mid(h,13,1)=chr(65+x12 mod 14)
    If InStr(h,chr(65+x12 mod 14))<13 Then iterate
    For x13=0 to 23
    If Asc(pot(x12),2)=Asc(pot(x13),1) Then
    mid(h,14,1)=chr(65+x13 mod 14)
    If InStr(h,chr(65+x13 mod 14))<14 Then iterate

    MsgBox s(Asc(pot(x00),1)-48)+" - "+s(Asc(pot(x00),2)-48)+","+_
    s(Asc(pot(x01),1)-48)+" - "+s(Asc(pot(x01),2)-48)+","+_
    s(Asc(pot(x02),1)-48)+" - "+s(Asc(pot(x02),2)-48)+","+_
    s(Asc(pot(x03),1)-48)+" - "+s(Asc(pot(x03),2)-48)+","+_
    s(Asc(pot(x04),1)-48)+" - "+s(Asc(pot(x04),2)-48)+","+_
    s(Asc(pot(x05),1)-48)+" - "+s(Asc(pot(x05),2)-48)+","+_
    s(Asc(pot(x06),1)-48)+" - "+s(Asc(pot(x06),2)-48)+","+_
    s(Asc(pot(x07),1)-48)+" - "+s(Asc(pot(x07),2)-48)+","+_
    s(Asc(pot(x08),1)-48)+" - "+s(Asc(pot(x08),2)-48)+","+_
    s(Asc(pot(x09),1)-48)+" - "+s(Asc(pot(x09),2)-48)+","+_
    s(Asc(pot(x10),1)-48)+" - "+s(Asc(pot(x10),2)-48)+","+_
    s(Asc(pot(x11),1)-48)+" - "+s(Asc(pot(x11),2)-48)+","+_
    s(Asc(pot(x12),1)-48)+" - "+s(Asc(pot(x12),2)-48)+","+_
    s(Asc(pot(x13),1)-48)+" - "+s(Asc(pot(x13),2)-48)+chr(13)+h


    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    End If
    Next
    Next


    MsgBox "That's all Thomas - After"+str(int(timer-ti)

    End Function





Hvalabogu, se mi source semiavtomatično zgenerira. Zato tudi tisti narekvaji okrog Moj

;)

Thomas ::

Ampak tukaj se išče Eulerjev in ne Hamiltonov obhod. Zanj res velja:

A connected graph has an Eulerian trail iff it has at most two vertices of odd degree

(Moj program obdeluje oboje.)

No, Eulerjev obhod gre po vsaki poti enkrat, Hamiltonov pa v vsako točko enkrat.

Eulerjev je hitro rešljiv, če sploh obstaja, je. Ne pa KATERI je.

A vi mene razumete? :D

Man muss immer generalisieren - Carl Jacobi

.:joco:. ::

Skoraj... Pravzaprav ne čist.

Kaj sta to Eulerjev obhod in Hamiltonov obhod in kako zdej na hitro zvedet če je uganka rešljiva?
"Is science true?"
You don't get it.
Science is the process of trying to find out what's true.

Thomas ::

Euler gre po vseh poteh enkrat. Hamilton pa skozi vsako vozlišče enkrat.

Prvi lahko obišče kakšno vozlišče večkrat. Drugi pa lahko kakšno pot kar izpusti.

:)
Man muss immer generalisieren - Carl Jacobi

.:joco:. ::

Ja, potem je prvi malo bolj pravilen, ne?
"Is science true?"
You don't get it.
Science is the process of trying to find out what's true.

Lucifix ::

No a ste kr pozabl da je treba to rešt? Še zdej nism dubu znanstveno potrjenega odgovora! :D

Brane2 ::

Dobu si odgovor, kokr se spomnim: rešitve ni !

tao_s ::

hm.. kolikor sem razumel razlago o teh uporabljenih algoritmih se tudi teh pik ne bi dalo povezat s (mislim da) štirimi potezami, ne da bi dvignili svinčnik (torej sklenjena črta, tri oglišča)



O O O
O O O
O O O

Zgodovina sprememb…

  • spremenil: tao_s ()

Ziga Dolhar ::

Seveda se da...

__a__b__c__(d)
1
2
3
(4)

d in 4 sta vrstica in stolpec brez kroglic.

A1 > A4 > D1 > A1 > C3

OS G ::

Pri teh pikah sploh ni možno imeti tri ogljišča in da bi v štirih potezah povezu 9 točk.
Je pa možno z večimi potezami povezat in da ima več ogljišč samo da ne rišeš po istih črtah in ne dvigneš svinčnika.
>:D
Prosim, kištica prižgi se! Prosim, kištica prižgi se! Opps! Ti si moja velika kišta.
Prosim velika kišta prižgi se! Bzzzzzzzzz. TO!?!?

tao_s ::

OS G: seveda se da, rešitev maš en post pred tabo... podatki so pravilni: 4 poteze, 3 ogljišča!

Zanima me samo, če tak algoritem to rešitev najde ali ne? Ker če je ne, potem se bomo še malo zajebavali s prvotno zastavljeno uganko :D

OS G ::



tole je njegova resitev ki niti slucajno ni pravilna;((
Prosim, kištica prižgi se! Prosim, kištica prižgi se! Opps! Ti si moja velika kišta.
Prosim velika kišta prižgi se! Bzzzzzzzzz. TO!?!?

Matek ::

Ta rešitev je popolnoma pravilna, zakaj naj po tvojem mnenju ne bi bila OS G, poteze so 4, oglišča so 3.
Bolje ispasti glup nego iz aviona.

OS G ::

MadManMato ce ne vidis strli ena daljica ven iz lika kar naredi novo ogljisce kar pomeni da ima lik 4 ogljišča.;((
Prosim, kištica prižgi se! Prosim, kištica prižgi se! Opps! Ti si moja velika kišta.
Prosim velika kišta prižgi se! Bzzzzzzzzz. TO!?!?

.:joco:. ::

tao_s, Ziggga, MadManMato very good thinking8-)

Thomas -> naredi program!:D
"Is science true?"
You don't get it.
Science is the process of trying to find out what's true.

Lucifix ::

Moj bog! Jst sm pa mislu da se boste vsi zajeb... s svinčnikom in praznim papirjem kokr jst!!! ;( Hehe

.:joco:. ::

Sicer je res, da ne rišeš lika, ampak samo povezuješ točke.:|
"Is science true?"
You don't get it.
Science is the process of trying to find out what's true.

Ziga Dolhar ::

Pardon me, kako boš s štirimi črtami naredil lik, ki bo imel tri ogljišča?

Aja, razen če bi bil kot trikotnik, 4. daljica pa bi bila "višina" na daljico.

tao_s ::

pa kaj ti narišem :D

a b c d
OOO o
OOO o
OOO o
o o o o

s črto greš ven iz kvadrata!

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

FIZIKA, pomoč!

Oddelek: Šola		51477 (1034) Unilseptij
»

Pot z avtom za 3 clansko druzino z avtom iz Ljubljane do Barcelone (strani: 1 2 3 )

Oddelek: Loža		10322173 (19148) peko_deko
»

algoritm za pot med dvema točkama

Oddelek: Programiranje		161683 (1376) detroit
»

Uganka

Oddelek: Loža		111657 (1490) McHusch
»

Problemi s TEAC CD-W540E

Oddelek: Strojna oprema		211932 (1568) Dami

Več podobnih tem