-
Pranešimai
247 -
Užsiregistravo
-
Lankėsi
-
Atsiliepimai
100%
Turinio tipas
Forumas
Kalendorius
Parduotuvė
Akademija
Skelbimai
Valuediz Pranešimai
-
-
Pradžiai užmiršk viską, ką čia perskaitei su "geriau už perrinkimą nerasi". :)
Na, o dabar galim pradėti. Tavo uždavinys yra vienas iš standartinių dinaminio programavimo problemų. Čia gali rasti paaiškinimą (vadinasi "balanced partition").
Trumpai apie dinaminį programavimą (DP)
Pirmiausia DP nėra koks tai mandrus algoritmas, tai grynai matematikos sritis (priklauso diskrečiąjai optimizacijai) ir su tokiu programavimu, kurį visi (išskyrus matematikus) turi galvoje, turi tik tai bendro, jog dažnai taikomas įvairiose situacijose.
DP veikimą gali interpretuot įvairiai - pasirink kaip tau pačiam paprasčiau pavyksta įsivaizduoti. Keletas pavyzdžių:
- Šokinėjimas per būsenas
- Kelių dimensijų lentelės pildymas
- Rekursijos medis, skaičiuojamas nuo priešingos pusės
- Perrinkimas su netinkamų (nelogiškų) variantų išmetimu vykdymo metu
Tačiau, kad ir kokią interpretaciją pasiimtum, rezultatas tas pats - jis tiesiog didelę problemą skaido į mažesnes tokias pat problemas ir pagal tų mažesnių problemų rezultatą paskaičiuoja savo reikšmę.
Dažniausiai DP problema sprendžiama tokiu eiliškumu:
- Sudarant vieną (arba kelias) rekurentinę formulę (ją paprastai gali apsirašyti daugiamačiu masyvu).
- Apsibrėžiant pradines ir kraštines sąlygas
- Skaičiuojant pagrindinį uždavinį, aprašytą ta pačia rekurentine formule.
- Išskiriant problemos sprendinį iš praeitame etape užpildytos lentelės (daugiamačio masyvo, pildomo pagal rek. formulę)
Kartais (priklauso nuo problemos) gali išsirinkti daugiau sprendinių (keisdamas įeinamus problemos duomenis) neperskaičiuodamas pagrindinio uždavinio etapo. Čia aprašiau gan siaurą problemų tipą, pasitaiko ir kurkas sudėtingesnių atvejų.
Grįžkim prie tavo problemos.
Ją galime perfrazuoti:
Reikia rasti 2 krūvas, kurias įvardinsime jų narių sumomis - pavadinkim krūva (k) ir krūva (s-k), čia s - visų aibės narių suma. Tuomet mums reikia nustatyti sumą k taip, jog:- Ji būtų išreiškiama duotos multi-aibės nariais (čia bus reikalingas DP)
- Skirtumas abs( (s-k) - (k) ) būtų minimalus
Sprendimas.
Pažymėkim duotą multi-aibę raide d ir jos narių skaičių raide n.
Absibrėškime rek. formulę fx(y) = max{ fx-1(y), fx-1(y-d(x)) }
Čia x - koordinatės kintamasis multi-aibėje, o y - būsenos kintamasis.
Jos veikimą gali interpretuoti, kaip "imti-neimti". Nors tokia interpretacija ne visai teisinga, tačiau padės įsivaizduoti veikimą susiejant su paprastesne problema (knapsack).
Toliau mums reikės pradinės salygos - visiems x, priklausantiems [0,n-1], nustatome fx(0) = 1
Rezultatu galime laikyti fn-1(k) reikšmes, kurios nurodys ar krūvą (k) galime išreikšti multi-aibės d elementais.
Galiausiai, mums beliko rasti tokį k, kuris tenkina sąlygą fn-1(k) ir su kuriuo krūvų skirtumas yra minimalus.
Programos kodas
Programoje specialiai pasirinkau ekvivalentų rekurentinės funkcijos bool vaizdavimą, vietoje {1,0}. Gal taip paprasčiau bus suvokti.
#include <stdio.h> using namespace std; int main() { int sum, min_diff, min_k, d[] = { 5, 9, 8, 3 }, n = 4; //aibes nariu suma sum = 0; for(int i = 0; i < n; i++) { sum += d[i]; } //apsibreziame ir nuresetiname lentele bool **f = new bool*[n]; for(int i = 0; i < n; i++) { f[i] = new bool[sum+1]; for(int j = 0; j <= sum; j++) { f[i][j] = false; } } //pradine salyga for(int x = 0; x < n; x++) { f[x][0] = true; } //pagrindinis skaiciavimas for(int x = 1; x < n; x++) { for(int y = 1; y <= sum; y++) { f[x][y] = ( f[x-1][y] || (y-d[x] >= 0 && f[x-1][y-d[x]]) ); } } //ieskome maziausio skirtumo tarp kruvos (k) ir kruvos (s-k), kuris tenkina salyga f[n-1][k] min_diff = sum; min_k = 0; for(int k = 1; k <= sum/2; k++) { if(f[n-1][k] && min_diff > sum - 2*k) { min_diff = sum - 2*k; min_k = k; } } printf("%d %d\n", min_k, sum - min_k); return 0; }
Dabar krūvų sumos yra žinomos, beliko tik rasti būtent kurie nariai jas gali sudaryti. Čia turėtum be vargo susitvarkyti. :)
- Šokinėjimas per būsenas
-
-
Pažymėkime
a - skaičius 2ct monetų sumoje
b - skaičius 5ct monetų sumoje
Tada sumą galime užrašyti: 81 = 2*a + 5*b
Išreiškiame a: a = (81 - 5*b)/2
Žinome, kad a ir b turi būti sveikieji skaičiai. Matome, jog b turi būti nelyginis skaičius, toks, kad (1 <= b <= 15).
[ nes kai b = 1: (81 = 2*38 + 5*1) ir kai b = 15: (81 = 2*3 + 5*15) ]
Taigi b reikšmių gali būti 8.
Ats.: 8.
-
Jei gerai supratau užduotį, tai turėtų užtekti vien SQL ir nieko daugiau. DB-Class panašių uždavinių yra (priklauso ką laikai "tinkamiausia pora").
-
Gal galite padeti ir pasakyti, kaip turetu atrodyti ciklas, kuris uzeitu ant pagrindines istrizaines (nuo virsutinio desinio kampo iki kairio kampo apacios) ir prieitu prie tu elementu, kurie yra virs jos. Niekaip neiseina isburt sito reikalo.
Čia aprašei šalutinę įstrižainę.
Duotajam kvadratiniam dvimačiam masyvui:
Suskaičiuoti kiekvienos eilutės teigiamų elementų, esančių virš pagrindinės įstrižainės, aritmetinius vidurkius.
for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { //tikrini ar A[i][j] teigiami } }
-
Kaip pirmas bandymas, labai neblogai. :) O dabar kritika...
Keletas pastebėjimų:
- Kur logotipas?
- Apie kiekvieną elementą nebūtina dėti "dėžutės"
- Tarpai tarp dėžučių dėti visiškai iš akies, t.y. vienur viskas sugrūsta, o kitur tušti plotai.
- Nėra bendro puslapio pločio, t.y. viena dizaino dalis yra ~780px, kita ~830px pločio.
- Kas susiję su turiniu(tekstas, pavadinimai, ikonos,...) - viskas atrodo blogai.
- "Skaityti daugiau" atrodo lyg paieškos laukeliai.
Patarimai:
- Naudok liniuotes.
- Daugiau detalių. Net 1px turi labai didelę reikšmę bendram vaizdui.
- Pradžioje su balta(#fafafa , #f2f2f2) spalva ir švelniais pilkos atspalviais lengviau dirbti. Tik tereikia kontrastingų detalių.
- Nedėk visokių ikonų, paveiksliukų vien tam, kad užpildytum tuščias vietas.
- Praleisk daugiau laiko prie vieno konkretaus dizaino, t.y. bent kelias dienas po pirmo varianto nupiešimo kiekvieną rytą atsikėlęs pažiūrėk kaip jis dabar tau atrodo ir iškart užklius kas nors, o tada perpieši. Taip greičiau tobulėsi, nei kepdamas vis naujus dizainus kasdien.
- Kur logotipas?
-
Kaip pradedančiajam, http://projecteuler.net/ bus kaip tik.
-
Pirmiausia turėtum nueiti į fakulteto(į kurį nori pereiti) administraciją ir visko išsiklausinėti: ar reikės mokėti už išlyginamąsias(modulius kurių neturėjai ir yra svarbūs), kokie ir kiek jų būtų, ar yra galimybė juoss turėti lygiagrečiai, ar neprarasi krepšelio, dėl studijų kainų skirtumo(jeigu pereini iš brangesnių į pigesnes tai nesvarbu), dėl studijų srities keitimo pvz. fiziniai mokslai -> technologiniai mokslai ir panašių dalykų..
Aš pats perėjau iš informatikos į taikomąją matematiką po 3semestrų. Tai buvo situacija, jog buvusiame fakultete prisakė visokių dalykų, kad tik atbaidytų nuo perėjimo, jog reikės daug mokėti, pirktis visus modulius ir pan., tačiau buvo visiškai kitaip. Todėl geriau pasitikėk fakultetu į kurį pareini. :)
-
Žodžiu situacija tokia: reikia maksimum iš informatikos, kad įstoti į užsieni. Kaip visi žinome egzas dalijasi į dvį dalis: testas ir programavimas.
Testą padarau neblogai, apie 90%, problemos ten kur nesuprantu žodžių reikšmės, nes mokausi rusų mokykloje bei kitose sunkiuose klausimose. Klausimas, kaip beveik maksimumui pasiruošti šiam testui?
Toliau programavimas, šiaip problemų nėra, bet nevisada padarau, reikia daugiau praktikos, visas VBE užduotys išsprendžiau, kur gaut dar?
Nerašykit, paklausk mokytojos, nes dėl kai kurių priežaščių, manau, kad ji maksimumui neparuoš. Žodžių laukiu jūsų patarimų :)
Teorinę dalį galima ir per paskutinę dieną išmokti. Užtenka VBE pražiūrėti, na dar gali kompiuterinio raštingumo testus išsispręsti. Kaip dėl programavimo, gali pabandyt olimpiadų, Kazicko konkurso uždavinius. Jie kiek sunkesni, bet jei mokėsi juos spręsti, tai egzamino uždaviniai bus labai lengvi.
Jeigu noresi, galesiu nufotografuot ir atsiust apie 30 puslapiu medziagos informatikai.
Pačiam analogiški klausimai su matematika. Informatika tikrai puikiai moku, tačiau matematika jau šis tas sunkiau. Realiai dabar 20 procentų kokių tesurenku..( < 30 taškų)
Dėl matematikos, rekomenduoju išsisprėsti visą Mockaus rudą uždavinyną ir turėtum iš egzamino bent ~90% gauti. O jei nori lygiai 100%, tai reikės kurkas daugiau darbo nei išsispręst 1 uždavinyną. :)
-
Dizainus gali piešti tiek su photoshop, tiek su fireworks. Photoshop'as žymiai populiaresnis, tačiau tikrai atsiranda ir gerų dizainerių naudojančių fireworks. Priklauso kas tau patogiau. Beje, turėtų praversti ši nuoroda: http://webdesign.tutsplus.com/
-
Nuo savęs dar pridėčiau, jog labai svarbu skaityti svetimą kodą, ypač naujai kuriamų templeitų(tam gerai tinka tokios vietos kaip themeforest.net). Dėl perėjimo į kitą sritį irgi tiesą sako, savo kailiu patyriau :) Ilgesnį laiką tuom užsiiminėjant, ateina toks jausmas, jog pernelyg lėtai tobulėji ir vis mažiau įššukių sulauki, galbūt tai skatina keisti veiklą.
-
Kad jau patinka programavimas ir matematika, išbandyk sportinį programavimą, algoritmus :) gal užkabins. Tokiam amžiuje pradėjus, galima daug ką nuveikti. Jei domina plačiau, parašyk.
-
Dėkui tau, gerasis žmogau, atrodo pavyko ;)
3 kaip suprantu atsakymas 0?
Taip
-
3. Tiesiog apskaičiuoji, kad ir su trikampiais(plačiau).
4. Irgi apskaičiuoji ir gauni 2 vienodų narių sumą, kas ir reiškia, jog lyginis.
5. Apskaičiuoji ir gautą išraišką prisilygini 0, įstatai a=kb ir, iškeldamas b^2 prieš skliaustus, randi k.
-
-
Siūlau išbandyt programming challenges (pavyzdžiui: http://uva.onlinejudge.org/). Yra gan sudėtingų problemų, kurios labiau primena galvosūkius, bet reikalauja ir matematinių, programavimo žinių.
-
Siūlyčiau ruoštis vien programuot, geriausia būtų kokius sunkesnius uždavinius - iš olimpiadų(idealus variantas iš Kazicko konkurso). Išmokęs sunkesnius spręsti, tikrai neturėsi problemų su egzamininiais. Kaip dėl teorinės dalies, nemanau, kad ten reikia skirti daugiau 2 dienų prieš pat egzaminą. Aš būtent tokios taktikos praeitamet laikiaus ir išlaikiau visai neblogai :)
-
Kol kas tik pirmą dalį peržiūrėjau, tačiau jau žinau, kad žiūrėsiu viską dar kartą :D Geriausias seminaras, kurį esu matęs iki šiol, dėkui už jį. O visiems kitiems, rekomenduoju pažiūrėt!
-
Valuediz, o kaip tau su fizika sekasi? ;)
Nepasakyčiau, kad gerai(VBE 46), bet bandysiu ;)
-
Aš taip pat gavau ir jau išsiunčiau užpildytą atgal ;) Dėl pokalbio kažkaip nesijaudinu, kaip bus taip ;)
-
turiu klausima :)
siandien nueinu i ktu priemimo skyriu,padedu pora parasu,gaunu kazkoki lapeli apie banko pinigu pervedima ir daug reklamos. :) Taciau negavau jokio rimtesnio dokumento, nei sutarties ar panasiai..
dabar taip iseina, kad reikia eit i banka, o jame sumokejus 120lt vel grizt i priemimo skyriu ir is ju pasiimt kazkoki rimtesni dokumenta?
"Dokumentų Gavimo Pažymos" nedavė? Kaip supratau, tai ji ir yra tas dokumentas.
-
-
-
- WillFoldKK ir narto sureagavo į tai
- 1
- 1
Algoritmo problema
Programuotojų kampas
Atrašyta · Redagavo Valuediz
Taip, to nepaminėjau. :) Greitis atminties sąskaita. Na bent kol suma labai neišaugs programa tvarkysis gerai. Beje, lentelę palikau dvimatę tik vardan aiškumo, tai dimensijos, susijusios su elementų skaičiumi, galime nepaisyti ir tuomet gauname S baitų.