Part 2 Part 3 Part 4 Aku dijaluk nulis artikel iki kanthi tugas sing mbebayani saka pencarian Java Multithreading, sing, ora tanpa nggodha saka pangembang, diarani "tugas StringBuilder." Inti saka kahanan dheweke yaiku sakumpulan tembung (ing kondisi diwenehi jeneng kutha, sing kaya dolanan bocah-bocah) kudu disusun miturut prinsip domino, huruf pungkasan saka tembung n kudu. padha karo aksara pisanan saka tembung (n + 1) go, lan ngerti yen kabeh tembung diwenehi (individu) padha ditambahake munggah ing chain kuwi. Yen sampeyan bisa nggawe sawetara opsi kanggo rantai tembung sing dikarepake, sapa wae sing ditampa minangka solusi. Senadyan kesederhanaan lan kajelasan kondisi kasebut, ngrampungake masalah kasebut ora gampang, lan panggunaan StringBuilder ora bisa disimpen. Pangembang masalah kasebut dadi isomorf saka planet Linear Chaos, sing luwih saka sepisan wedi karo kadet JavaRush. Kaya sing dikarepake, solusi sing entheng ora cocog karo validator, amarga tansah ana rantai sing meksa algoritma naif kanggo ngliwati tembung. Perlu kanggo numpuk "kruk" tambahan, sing, nalika ngrampungake masalah, ora nggawa solusi sing luwih cedhak ing kasus umum lan nambah perasaan yen kondisi sing prasaja kudu duwe solusi sing padha. Aku kudu ngganti taktik lan nyilem sethithik menyang wilayah sing luwih dhasar. Ayo kula nggawe reservasi langsung yen aku ora nganggep aku minangka ahli ing teori grafik; topik sing bakal dakdemek meh ora ngluwihi ruang lingkup ngrampungake masalah tembung domino, kajaba mung bisa uga. saperangan saka digressions alam teoritis. Dadi, grafik. Apa iku grafik: iku kumpulan (set, set, dhaptar - apa wae) saka vertex sing disambungake . Sambungan biasane disebut pinggiran , vertex uga disebut simpul utawa simpul. Iki minangka grafik: Iki uga grafik: Yen kita bisa ngomong babagan pinggiran sing nduweni arah, mula grafik kasebut diarani berorientasi : Grafik ing rong gambar pisanan ora arah.. Kita bisa ngomong babagan pinggiran (u, v) identik karo pinggiran (v, u), yaiku, contone, pinggiran (0, 4) lan (4, 0) padha. Panah ing pinggiran grafik diarahake tegese pinggiran (u, v) minangka path saka vertex u kanggo vertex v lan pinggiran (v, u) ora ana. Ing gambar katelu ana pinggiran (E, A). Ora ana pinggiran (A, E). Ayo dideleng kanthi cetha ing gambar pungkasan. Sampeyan bisa sok dong mirsani sing vertex F ora ana pinggiran ing kabeh, iki cukup bisa. Kita uga nyathet yen pinggiran wis katon ing cedhak vertex A - loop, lan ing antarane vertex B lan D ana rong sudhut sing diarahake kanthi beda. Grafik sing diarahake ngidini artefak kasebut. Ayo ngomong yen grafik kasebut nggambarake klompok kenalan sing menehi hadiah saben liyane. Kita weruh yen F sing rakus ora menehi apa-apa marang sapa wae, B lan D ijol-ijolan hadiah (kajaba saben wong menehi hadiah kanggo wong liya), lan A menehi hadiah kanggo awake dhewe, mesthine nalika sukses ngrampungake masalah. masalah saka planet Linear Chaos. Miturut cara, elinga yen vertices saka graph ora kudu nomer utawa ngemot nomer, iku rodo wadhah, i.e. padha bisa nyimpen sembarang obyek. Grafik minangka gambaran saka sambungan. Istilah penting sing bakal migunani kanggo kita mengko - jumlah pinggiran sing dipasang ing vertex (utawa, kaya sing diucapake, kedadeyan kasebut) diarani derajat vertex sing diwenehake. Contone, ing gambar pisanan, vertex 0 duwe gelar 2, 1 duwe gelar 4, 3 duwe gelar 3, vertex 0 saka tokoh kapindho duwe gelar 1. Ing artikel iki kita ora bakal nliti macem-macem jinis grafik, kita mung bakal sebutno sing ana uga grafik bobot, iku. sing nomer tartamtu ditempelake ing saben pinggiran, kang nuduhake "rega" sawijining wacana. Grafik sing disambungake duwe sawetara subtipe, sing dibedakake karo sifate. Contone, grafik sing pinggiran ora mbentuk siklus ngendi wae diarani wit (padha duwe kulawarga menarik karo jeneng apik tenan kaya "wit abang-ireng," contone) lan digunakake digunakake ing macem-macem algoritma penting lan struktur data. Nggunakake grafik kanggo ngatasi masalah Kabeh iki menarik banget, sampeyan ngomong, nanging apa kabeh iki kudu apa karo mbangun chain saka tembung? Pranyata sing paling langsung iku. Ayo deleng conto tes saka kondisi: { Amsterdam Melbourne New York Kyiv Vienna }. Ayo nulis ing sembarang urutan huruf "nodal" sing tembung nempel ing: {A, M, N, K, B} lan sambungake karo tembung. Kaya sing bisa dideleng, kita duwe grafik terarah sing titik kasebut minangka huruf. lan pinggiran iku tembung, nyambungake. Yen kita nemokake cara kanggo ngliwati kabeh sudhut saka vertex menyang vertex supaya kita ngunjungi saben pinggiran mung sapisan, masalah kita bakal ditanggulangi. Ayo nyoba nyebarake simpul ing diagram kanthi cara sing beda: Saiki kita bisa ndeleng manawa grafik kita minangka loop tertutup. Kita bisa miwiti urutan kanthi tembung apa wae, lan bakal dadi keputusan sing tepat. Nanging, kondisi masalah kasebut ngandhani yen solusi siji wae bakal cukup. Ayo ngganti Vena karo Vladimir: Kita ndeleng rong akibat: pisanan, kita kudu nambah vertex anyar, huruf P, lan kapindho, kita weruh sing ora bisa maneh kanggo daur ulang grafik kita. Ayo diringkes kabeh ing ndhuwur lan ngenalake rong istilah anyar: 1. Grafik sambung sing pinggire bisa dilewati kanthi ngunjungi saben siji mung sapisan diarani grafik sing ngemot "jalur Eulerian" . Fitur saka grafik kasebut (kajaba ora ana simpul tanpa pinggir) yaiku tingkat genap kabeh simpul kajaba loro (lan mung loro). 2. Yen ternyata bisa bali menyang simpul asli, kita ngomong yen ana "siklus Eulerian" ing grafik . Fitur saka grafik kasebut (kajaba ora ana simpul tanpa pinggir) yaiku tingkat rata saka kabeh simpul. Coba bayangake dhaptar kutha kaya iki: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Ayo mbangun grafik: Ing diagram sampeyan bisa ndeleng manawa grafik iki nduweni jalur Eulerian. Mung ana rong simpul kanthi gelar ganjil - yaiku M lan L, liyane genap: A duwe gelar 4, amarga daur ulang diitung kaping pindho, lan P lan Y duwe gelar 2. Yen kita teka munggah karo algoritma sing bisa mbangun rute Eulerian adhedhasar rencana iki, ngandika, ing wangun dhaftar {M, A, A, P, Y. , L}, banjur kita bakal ngatasi masalah , amarga outputting tembung ing urutan tartamtu mung bakal dadi prakara technique. Mangkono, solusi kanggo masalah tembung domino kita mudhun kanggo ngetrapake algoritma kanggo nemokake jalur Eulerian (siklus kasebut "gratis") ing grafik sing diarahake. Sabanjure ->
Iki uga grafik: 
Yen kita bisa ngomong babagan pinggiran sing nduweni arah, mula grafik kasebut diarani berorientasi : 
Grafik ing rong gambar pisanan ora arah.. Kita bisa ngomong babagan pinggiran (u, v) identik karo pinggiran (v, u), yaiku, contone, pinggiran (0, 4) lan (4, 0) padha. Panah ing pinggiran grafik diarahake tegese pinggiran (u, v) minangka path saka vertex u kanggo vertex v lan pinggiran (v, u) ora ana. Ing gambar katelu ana pinggiran (E, A). Ora ana pinggiran (A, E). Ayo dideleng kanthi cetha ing gambar pungkasan. Sampeyan bisa sok dong mirsani sing vertex F ora ana pinggiran ing kabeh, iki cukup bisa. Kita uga nyathet yen pinggiran wis katon ing cedhak vertex A - loop, lan ing antarane vertex B lan D ana rong sudhut sing diarahake kanthi beda. Grafik sing diarahake ngidini artefak kasebut. Ayo ngomong yen grafik kasebut nggambarake klompok kenalan sing menehi hadiah saben liyane. Kita weruh yen F sing rakus ora menehi apa-apa marang sapa wae, B lan D ijol-ijolan hadiah (kajaba saben wong menehi hadiah kanggo wong liya), lan A menehi hadiah kanggo awake dhewe, mesthine nalika sukses ngrampungake masalah. masalah saka planet Linear Chaos. Miturut cara, elinga yen vertices saka graph ora kudu nomer utawa ngemot nomer, iku rodo wadhah, i.e. padha bisa nyimpen sembarang obyek. Grafik minangka gambaran saka sambungan. Istilah penting sing bakal migunani kanggo kita mengko - jumlah pinggiran sing dipasang ing vertex (utawa, kaya sing diucapake, kedadeyan kasebut) diarani derajat vertex sing diwenehake. Contone, ing gambar pisanan, vertex 0 duwe gelar 2, 1 duwe gelar 4, 3 duwe gelar 3, vertex 0 saka tokoh kapindho duwe gelar 1. Ing artikel iki kita ora bakal nliti macem-macem jinis grafik, kita mung bakal sebutno sing ana uga grafik bobot, iku. sing nomer tartamtu ditempelake ing saben pinggiran, kang nuduhake "rega" sawijining wacana. Grafik sing disambungake duwe sawetara subtipe, sing dibedakake karo sifate. Contone, grafik sing pinggiran ora mbentuk siklus ngendi wae diarani wit (padha duwe kulawarga menarik karo jeneng apik tenan kaya "wit abang-ireng," contone) lan digunakake digunakake ing macem-macem algoritma penting lan struktur data. Nggunakake grafik kanggo ngatasi masalah Kabeh iki menarik banget, sampeyan ngomong, nanging apa kabeh iki kudu apa karo mbangun chain saka tembung? Pranyata sing paling langsung iku. Ayo deleng conto tes saka kondisi: { Amsterdam Melbourne New York Kyiv Vienna }. Ayo nulis ing sembarang urutan huruf "nodal" sing tembung nempel ing: {A, M, N, K, B} 
lan sambungake karo tembung. 
Kaya sing bisa dideleng, kita duwe grafik terarah sing titik kasebut minangka huruf. lan pinggiran iku tembung, nyambungake. Yen kita nemokake cara kanggo ngliwati kabeh sudhut saka vertex menyang vertex supaya kita ngunjungi saben pinggiran mung sapisan, masalah kita bakal ditanggulangi. Ayo nyoba nyebarake simpul ing diagram kanthi cara sing beda: 
Saiki kita bisa ndeleng manawa grafik kita minangka loop tertutup. Kita bisa miwiti urutan kanthi tembung apa wae, lan bakal dadi keputusan sing tepat. Nanging, kondisi masalah kasebut ngandhani yen solusi siji wae bakal cukup. Ayo ngganti Vena karo Vladimir: 
Kita ndeleng rong akibat: pisanan, kita kudu nambah vertex anyar, huruf P, lan kapindho, kita weruh sing ora bisa maneh kanggo daur ulang grafik kita. Ayo diringkes kabeh ing ndhuwur lan ngenalake rong istilah anyar: 1. Grafik sambung sing pinggire bisa dilewati kanthi ngunjungi saben siji mung sapisan diarani grafik sing ngemot "jalur Eulerian" . Fitur saka grafik kasebut (kajaba ora ana simpul tanpa pinggir) yaiku tingkat genap kabeh simpul kajaba loro (lan mung loro). 2. Yen ternyata bisa bali menyang simpul asli, kita ngomong yen ana "siklus Eulerian" ing grafik . Fitur saka grafik kasebut (kajaba ora ana simpul tanpa pinggir) yaiku tingkat rata saka kabeh simpul. Coba bayangake dhaptar kutha kaya iki: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Ayo mbangun grafik: 
Ing diagram sampeyan bisa ndeleng manawa grafik iki nduweni jalur Eulerian. Mung ana rong simpul kanthi gelar ganjil - yaiku M lan L, liyane genap: A duwe gelar 4, amarga daur ulang diitung kaping pindho, lan P lan Y duwe gelar 2. Yen kita teka munggah karo algoritma sing bisa mbangun rute Eulerian adhedhasar rencana iki, ngandika, ing wangun dhaftar {M, A, A, P, Y. , L}, banjur kita bakal ngatasi masalah , amarga outputting tembung ing urutan tartamtu mung bakal dadi prakara technique. Mangkono, solusi kanggo masalah tembung domino kita mudhun kanggo ngetrapake algoritma kanggo nemokake jalur Eulerian (siklus kasebut "gratis") ing grafik sing diarahake. Sabanjure ->
GO TO FULL VERSION