Informaatika olümpiaadi põhikooli eelvoor – Jada seest numbri leidmine
http://www.teaduskool.ut.ee/orb.aw/class=file/action=preview/id=6379/poh.et.pdf
3. Jada - 1 sekund - 50 punkti
Vaatleme (lõpmatut) numbrijada, mille saame kõigi positiivsete täisarvude kasvavas järjekorras üksteise järele kirjutamisega: 123456789101112131415...
Kirjutada programm, mis leiab selles jadas positsioonidel N ja N + 1 olevad numbrid.
Sisend. Tekstifaili jada.sis ainsal real on täisarv N (1 <= N <= 109).
Väljund. Tekstifaili jada.val ainsale reale väljastada kaks numbrit — jada otsitavad elemendid. Numbrid väljastada vahetult üksteise kõrvale, ilma tühikuteta.
| Näide. jada.sis 5 | jada.val 56 |
| Näide. jada.sis 14 | jada.val 12 |
Hindamine. Testides summaarse väärtusega 30 punkti on N <= 106 ja nende hulgas testides summaarse väärtusega 15 punkti on N <= 103.
Selle lahenduse väljamõtlemine oli kõige keerulisem. Siin tekkis mitu lahendusvarianti kuid kas alljärgnev on kõige efektiivsem, selles pole ma kindel. Sisetunne ütleb, et seda saaks intelligentsemalt teha, kuid minu arvuridade seaduspärade õppimine on üsna kaugesse kooliaega libisenud seega lähenesin nö. “brutal force” meetodil ülesande lahendamisele.
Alljärgnevaga on ülesanne lahendatud, aga äkki on kellelgi parem meetod?
- #include <stdio.h>
- FILE *jada, *valf;
- int _tmain(int argc, _TCHAR* argv[])
- {
- int temp;
- int sisend;
- int i;
- int tulemus;
- int jrk;
- int end = 0;
- jada = fopen("jada.sis", "r");
- fscanf( jada, "%i", &sisend);
- for(i=1; i<100000000; i++)
- {
- temp = i;
- jrk = 0;
- //järgmise while tsükli abil saame teada mis number on sisend positsioonil
- //ja mitmendal kohal antud numbri sees on otsitav arv
- while(temp > 0) {
- temp = temp/10;
- end++;
- jrk++;
- if(end == sisend)
- break;
- }
- if(end == sisend)
- break;
- }
- //saame teada numbri positsioonide arvu
- temp = i;
- end = 0;
- while(temp > 0) {
- temp = temp/10;
- end++;
- }
- //vastavalt postisioonile leiame numbri seest arvu
- temp = i;
- for(int k = jrk; k <= end; k++)
- {
- tulemus = temp%10;
- temp = temp/10;
- }
- printf("arv on %i\n", tulemus);
- valf = fopen("jada.val", "w");
- fprintf(valf, "%i%i\n", tulemus, tulemus+1);
- fclose(valf);
- return 0;
- }