Valuediz

Pamiršai paminėti, kad šis algortimas tinka, kai skaičiai maži ir jų ne itin daug, nes atminties sanaudos n*S baitų (čia n – elementų skaičius, S – jų suma). Kitu atveju atminties sąnaudos išauga nežmoniškai. Pavyzdžiui, turint vien tik {2147483647} (maksimalus skaičius, telpantis į signed int) programa surytų beveik 2GB! atminties. Žinoma, taip nebus, nes tiek atminties kompiuteris nesugebės alokuoti ir programa nebaigs vykdymo.

 

Kaip buvo minėta, problema NP-pilna. Dinaminis algoritmas tinkamas tik uždavinio sąlygai su atitinkamais apribojimais.

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ų.

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:

1. Sudarant vieną (arba kelias) rekurentinę formulę (ją paprastai gali apsirašyti daugiamačiu masyvu).
   
2. Apsibrėžiant pradines ir kraštines sąlygas
   
3. Skaičiuojant pagrindinį uždavinį, aprašytą ta pačia rekurentine formule.
   
4. 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ę f_x(y) = max{ f_x-1(y), f_x-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 f_x(0) = 1

Rezultatu galime laikyti f_n-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ą f_n-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. :)

• 
   
  
• Into the Wild
  
• 127 hours
  
• Seven Pounds
  
• Good Will Hunting
  
• Proof
  
• A Beautiful Mind
  
• 21
  
• Million Dollar Baby
  
• August Rush
  
• The Aviator
  
• The Social Network
  
• Pirates of Silicon Valley
   
  

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ų:

1. Kur logotipas?
   
2. Apie kiekvieną elementą nebūtina dėti "dėžutės"
   
3. Tarpai tarp dėžučių dėti visiškai iš akies, t.y. vienur viskas sugrūsta, o kitur tušti plotai.
   
4. Nėra bendro puslapio pločio, t.y. viena dizaino dalis yra ~780px, kita ~830px pločio.
   
5. Kas susiję su turiniu(tekstas, pavadinimai, ikonos,...) - viskas atrodo blogai.
   
6. "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.
  

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.

Kaip matau, nemažai informatikų čia :o

KTU 612I10004 0620 informatika vf NL 19.72 19.72 kvietimas, NL

Va ir mano :)

Tikriausiai susitiksim :D