DIG Digital Corner
Alles wat je altijd al over computers, hardware, software, internet en elektronische gadgets had willen weten, maar niet op Tweakers.net durft te vragen.
Dat is in C toch niet heel veel moeilijker?quote:Op donderdag 14 juni 2012 10:07 schreef ralfie het volgende:
[..]
[ code verwijderd ]
Vergeleken met c++ is C# zoo makkelijk.
| 1 2 3 4 5 6 7 8 | char tmp[33]; char outp[1024] = {0}; for(char *c=in; *c; c++) { strcat(outp, "-"); strcat(outp, itoa(toupper(*c)-'A'+1, tmp, 10)); } return strdup(&outp[1]); |
Ha, nu wil ik ook meedoen met een echte C++ oplossing:
Ik vind het wel wat hebben.
| 1 2 3 4 5 | std::string encode(std::string const &input) { std::ostringstream ss; std::for_each(input.begin(), input.end(), [&ss](char c){ ss << c - 96 << '-'; }); return ss.str(); } |
Ik vind het wel wat hebben.
"Slechts diegene mag slopen die iets beters kan bouwen."
Je vergeet de laatste '-' eraf te strippen, en een toupper/tolower ergens 
Maar goed: de algemene aanpak in C, C++ en C# is hetzelfde; zitten wat kleine API/syntax verschillen in, maar ik zie niet waarom het ene fundamenteel makkelijker zou zijn dan het andere
Maar goed: de algemene aanpak in C, C++ en C# is hetzelfde; zitten wat kleine API/syntax verschillen in, maar ik zie niet waarom het ene fundamenteel makkelijker zou zijn dan het andere
Volgens de opgave is de input altijd in kleine letters en mag de laatste '-' blijven staan. Wel lezen he?quote:Op donderdag 14 juni 2012 13:11 schreef Ai_KaRaMBa het volgende:
Je vergeet de laatste '-' eraf te strippen, en een toupper/tolower ergens
Maar je hebt gelijk, natuurlijk. De oplossingen zijn precies hetzelfde. De programmeertaal is voorkeur.quote:Maar goed: de algemene aanpak in C, C++ en C# is hetzelfde; zitten wat kleine API/syntax verschillen in, maar ik zie niet waarom het ene fundamenteel makkelijker zou zijn dan het andere
"Slechts diegene mag slopen die iets beters kan bouwen."
quote:
[..]
[ code verwijderd ]
Vergeleken met c++ is C# zoo makkelijk.
| 1 | return "-".join([str(ord(c) - ord("a") + 1) for c in string]) |
[ Bericht 1% gewijzigd door thabit op 14-06-2012 15:06:10 ]
Oh, ik had de opgave niet gelezen... Ik had mijn code gelijk getrokken aan die van ralfiequote:Op donderdag 14 juni 2012 13:13 schreef GS42 het volgende:
[..]
Volgens de opgave is de input altijd in kleine letters en mag de laatste '-' blijven staan. Wel lezen he?
Als je de opgave nog eens goed leest, dan zie je dat het weghalen van de laatste "-" punten oplevert.
Tsja, uiteindelijk doet Python het ook in C. Er zijn natuurlijk ook parsergeneratoren die het parsen van tekst prachtig doen, zoals de combinatie van Flex en Bison. Daarmee kan je tekst parsen in een soort meta-taaltje waarna de parsergenerator de broncode voor je genereert en je zelf niets hoeft te schijven. De programma's worden daarom ook wel compiler-compilers genoemd.quote:Op donderdag 14 juni 2012 13:17 schreef thabit het volgende:
Nog makkelijker! String parsing moet je niet in C-watdanook willen doen.
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
"Slechts diegene mag slopen die iets beters kan bouwen."
Zeker, erg leuke site! Ik moet bekennen dat ik er uit zelfbescherming niet te vaak op zit, omdat ik anders hele dagen niks anders doe.quote:
[..]
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
Ik ken 't idd! Dat soort programmeer uitdagingen zijn trouwens altijd leuk.
Ik heb in het verleden ook wel deelgenomen aan USACO, TopCoder, Codecup en de ACM-ICPC (nooit verder gekomen dan de NWERC trouwens). Allemaal net wat anders van opzet, maar ook allemaal leuk om aan deel te nemen.
Helaas heb ik op het moment een beetje last van tijdgebrek
Ik heb in het verleden ook wel deelgenomen aan USACO, TopCoder, Codecup en de ACM-ICPC (nooit verder gekomen dan de NWERC trouwens). Allemaal net wat anders van opzet, maar ook allemaal leuk om aan deel te nemen.
Helaas heb ik op het moment een beetje last van tijdgebrek
Nee had ik nog nooit van gehoord maar zit er idd zeer interessant uit, ik ga na mijn tentamens denk ik maar eens even goed bekijken (als ik het er voor doe haal ik mijn tentamens waarschijnlijk niet meer)quote:
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
Beware of the Raping Zebra's
Ik heb als fysicus een c++ cursus gedaan op de universiteit.
En ik vind het altijd leuk om dummies te helpen.
En ik vind het altijd leuk om dummies te helpen.
Ik ben daar mee bezig met amd64 assembly en wiskunde, voor sommige heb je geen programma nodig.quote:
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
Ik ben pas begonnen met C++ te leren. Ik probeer het te doen aan de hand van die projecteuler site. Het is me gelukt de eerste drie vragen op te lossen. Het is misschien niet moeilijk als je weet hoe C++ in elkaar zit, maar voor mij is het een hele opgave (maar wel een leukequote:
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
).Ik ben nu aanbeland bij het volgende probleem:
Mijn aanpak is als volgt:quote:A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
1. Maak een functie die een getal opsplitst in zijn cijfers. Dus bvb: 123 --> 1, 2, 3
2. Maak een functie die het eerste en laatste cijfer vergelijkt, het tweede en het één na laatste, etc. Als die allemaal hetzelfde zijn dan is het een palindroom.
3. Genereer alle producten van 3 cijfers en pas 1. en 2. toe. (dat kan vast ook efficiënter)
Ik loop al vast bij stap 1. Het is me wel gelukt om die functie te maken, die van een getal 123 een array {1,2,3} maakt, alleen het lukt me niet om die in zijn geheel te "returnen". Ik heb ook van alles geprobeerd met pointers en vectors en van alles bij elkaar gegoogled, maar ik kom er maar niet verder mee.
Dit is mijn huidige code, waar ik ter illustratie een getal return. De hele array lukt niet, dus als iemand me daarmee kan helpen, graag!
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <iostream> #include <vector> using namespace std; //Deze functie bepaalt het aantal cijfers in een getal int numDigits(int q){ if(q>0 && q<10){return(1);}; if(q>9 && q<100){return(2);}; if(q>99 && q<1000){return(3);}; if(q>999 && q<10000){return(4);}; if(q>9999 && q<1000000){return(5);}; if(q>99999 && q<10000000){return(6);}; if(q>999999 && q<100000000){return(7);}; if(q>9999999 && q<1000000000){return(8);}; } //Deze functie splitst het getal op in zijn cijfers int digit(int p){ int z; int k(1); int l(1); int i(0); int m[numDigits(p)]; for(z=0; z<numDigits(p); z++){ k=(p/l)%10; l=10*l; m[i]=k; i++; } return m[1]; } int main(){ cout << digit(52); return 0; } |
Ik heb het zelf opgelost door het getal om te zetten naar een std::string en in de string het getal op palindromiteit te controleren. Dit is een mogelijkheid die je kunt overwegen. Ook kan je een std::vector gebruiken om de getallen in op te slaan. Een std::vector of std::string kan je beide gewoon returnen.quote:
Ik loop al vast bij stap 1. Het is me wel gelukt om die functie te maken, die van een getal 123 een array {1,2,3} maakt, alleen het lukt me niet om die in zijn geheel te "returnen". Ik heb ook van alles geprobeerd met pointers en vectors en van alles bij elkaar gegoogled, maar ik kom er maar niet verder mee.
Het is niet mogelijk een array te returnen uit een functie. Wel is het mogelijk een pointer naar een dynamisch gealloceerde array terug te geven, maar dit zou ik in dit geval niet aanraden.
Denk je dat je hiermee verder komt?
"Slechts diegene mag slopen die iets beters kan bouwen."
Met zo'n string is ook wel handig. Maar ik wil het proberen als array of vector (dan leer ik daar ook mee omgaan). Ik had al gevonden op internet dat je een array niet kon returnen en een vector wel, maar toch lukte het me niet met een vector.quote:
[..]
Ik heb het zelf opgelost door het getal om te zetten naar een std::string en in de string het getal op palindromiteit te controleren. Dit is een mogelijkheid die je kunt overwegen. Ook kan je een std::vector gebruiken om de getallen in op te slaan. Een std::vector of std::string kan je beide gewoon returnen.
Het is niet mogelijk een array te returnen uit een functie. Wel is het mogelijk een pointer naar een dynamisch gealloceerde array terug te geven, maar dit zou ik in dit geval niet aanraden.
Denk je dat je hiermee verder komt?
Ik heb bijvoorbeeld het volgende geprobeerd:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <iostream> #include <vector> using namespace std; //Deze functie bepaalt het aantal cijfers in een getal int numDigits(int q){ if(q>0 && q<10){return(1);}; if(q>9 && q<100){return(2);}; if(q>99 && q<1000){return(3);}; if(q>999 && q<10000){return(4);}; if(q>9999 && q<1000000){return(5);}; if(q>99999 && q<10000000){return(6);}; if(q>999999 && q<100000000){return(7);}; if(q>9999999 && q<1000000000){return(8);}; } //Deze functie splitst het getal op in zijn cijfers int digit(int p){ int z; int k(1); int l(1); int i(0); vector<int> m; for(z=0; z<numDigits(p); z++){ k=(p/l)%10; l=10*l; m.push_back(k); i++; } return m; } int main(){ cout << digit(52); return 0; } |
Maar dan krijg ik:
| 1 | error: cannot convert 'std::vector<int, std::allocator<int> >' to 'int' in return| |
Ah, dat is een vrij duidelijk foutmelding. Je weet dat je een functie begint door aan te geven welk type een functie returnt? Deze foutmelding geeft aan dat je een ander type teruggeeft dan volgens de functie-declaratie zou moeten. Dat klopt ook, want je schrijft int digit(), terwijl je een vector<int> teruggeeft. Dat moet veranderd worden.quote:
[..]
Met zo'n string is ook wel handig. Maar ik wil het proberen als array of vector (dan leer ik daar ook mee omgaan). Ik had al gevonden op internet dat je een array niet kon returnen en een vector wel, maar toch lukte het me niet met een vector.
Ik heb bijvoorbeeld het volgende geprobeerd:
[ code verwijderd ]
Maar dan krijg ik:
[ code verwijderd ]
Daarnaast kan je een vector niet afdrukken door deze gelijk in std::cout te stoppen. Jouw regel 35 kan dus ook niet: je zult de elementen van de vector 1 voor 1 af moeten drukken.
Verder gebruik je de vector echter op de juiste manier, dus dat zit goed. Er zijn nog wat andere op- en aanmerkingen, maar die zijn van minder belang. (Heb je toevallig eerder iets met C gedaan?)
"Slechts diegene mag slopen die iets beters kan bouwen."
Dank! Hier ben ik dus uren mee bezig geweest, heb geprobeerd in de return aan te geven dat hij een vector moet returnen, etc. En dan is het zo simpelquote:
[..]
Ah, dat is een vrij duidelijk foutmelding. Je weet dat je een functie begint door aan te geven welk type een functie returnt? Deze foutmelding geeft aan dat je een ander type teruggeeft dan volgens de functie-declaratie zou moeten. Dat klopt ook, want je schrijft int digit(), terwijl je een vector<int> teruggeeft. Dat moet veranderd worden.
. Heb geen ervaring met C. Heb alleen een beetje geprogrammeerd in Mathematica en Matlab.quote:Daarnaast kan je een vector niet afdrukken door deze gelijk in std::cout te stoppen. Jouw regel 35 kan dus ook niet: je zult de elementen van de vector 1 voor 1 af moeten drukken.
Verder gebruik je de vector echter op de juiste manier, dus dat zit goed. Er zijn nog wat andere op- en aanmerkingen, maar die zijn van minder belang. (Heb je toevallig eerder iets met C gedaan?)
Heb het nu ook eindelijk voor elkaar dat mijn code palindromen herkent en opslaat in een vector. Nu nog al die producten genereren, of iets slims gaan bedenken want ik weet niet hoe lang het duurt als ik ze allemaal ga genereren
Alle produkten van 2 driecijferige getallen controleren op palindroom zijn, dat zou op de meest naïeve wijze niet meer dan een fractie van een seconde moeten duren.quote:Op zaterdag 28 juli 2012 23:54 schreef thenxero het volgende:
Heb het nu ook eindelijk voor elkaar dat mijn code palindromen herkent en opslaat in een vector. Nu nog al die producten genereren, of iets slims gaan bedenken want ik weet niet hoe lang het duurt als ik ze allemaal ga genereren
Bij dit soort problemen kun je als vuistregel gebruiken dat je ongeveer 50 miljoen groepjes van simpele operaties per seconde kunt doen. Met brute force heb je minder dan 1k*1k = 1M mogelijkheden en de palindroom test vergt 6 stappen. Dus gaat makkelijk lukken binnen een seconde. Het is wel handig om zulk soort worst case analyses te doen, zeker als je een exponentieel algoritme hebt bedachtquote:
Heb het nu ook eindelijk voor elkaar dat mijn code palindromen herkent en opslaat in een vector. Nu nog al die producten genereren, of iets slims gaan bedenken want ik weet niet hoe lang het duurt als ik ze allemaal ga genereren
.Morgen ga ik ook weer eens project euler proberen, maar dan wel in python
.
quote:Op zondag 29 juli 2012 00:02 schreef thabit het volgende:
[..]
Alle produkten van 2 driecijferige getallen controleren op palindroom zijn, dat zou op de meest naïeve wijze niet meer dan een fractie van een seconde moeten duren.
Ah, handig zo'n vuistregel. Dan moet je waarschijnlijk wel wat beter programmeren dan dat ik het gedaan heb, want hier duurt het 21 secquote:Op zondag 29 juli 2012 00:43 schreef Wolfje het volgende:
[..]
Bij dit soort problemen kun je als vuistregel gebruiken dat je ongeveer 50 miljoen groepjes van simpele operaties per seconde kunt doen. Met brute force heb je minder dan 1k*1k = 1M mogelijkheden en de palindroom test vergt 6 stappen. Dus gaat makkelijk lukken binnen een seconde. Het is wel handig om zulk soort worst case analyses te doen, zeker als je een exponentieel algoritme hebt bedacht
Morgen ga ik ook weer eens project euler proberen, maar dan wel in python
. Hij geeft nu wel het goede antwoord. Waar gaat al die tijd heen?-code weg-
[ Bericht 13% gewijzigd door thenxero op 29-07-2012 10:35:51 ]
Ik denk dat het netter is om geen complete oplossingen te posten. Immers, andere mensen willen het ook zelf oplossen. Misschien kan je de code weghalen en vervangen door pseudo-code van de relevante gedeeltes?quote:
Ah, handig zo'n vuistregel. Dan moet je waarschijnlijk wel wat beter programmeren dan dat ik het gedaan heb, want hier duurt het 21 sec
[ code verwijderd ]
Maar als antwoord over waar al die tijd heen gaat: hoe vaak roep je digit() en numDigits() aan per getal dat je controleert? Zou je dat terug kunnen brengen?
En is er een snelle controle die je kunt doen om te kijken of je een getal [s] uberhaupt hoeft te controleren? Gecombineerd met deze lopmerking kan je ook wat tijd winnen door te bedenken waar het getal dat je zoekt zich waarschijnlijk bevindt in je zoekgebied en de zoekruimte in een andere volgorde doorlopen.
"Slechts diegene mag slopen die iets beters kan bouwen."
Geheugenallocatie is vrij duur en dat doe je nu juist heel vaak met de vector<int> in de digit() methode. Een bijkomend nadeel is dat je veel zogenaamde cache misses zult hebben. Een cpu kan data in lokaal geheugen (op de cpu zelf) opslaan om het later weer snel op te kunnen vragen. Maar als je de hele tijd nieuwe data maakt, kan de cpu er ook geen gebruik van maken.quote:
[..]
[..]
Ah, handig zo'n vuistregel. Dan moet je waarschijnlijk wel wat beter programmeren dan dat ik het gedaan heb, want hier duurt het 21 sec
[ code verwijderd ]
Heb het met die tips teruggebracht naar 0.4sec (die staan natuurlijk ook op EP, dus daar ging het eigenlijk niet om). Maar omdat thabit zei dat het op de meest naïeve manier nog een fractie van een seconde zou duren als je alle palindromen zou controleren, dacht ik dus dat er een soort fout in mijn code zat.
Maar als ik het goed begrijp kost het steeds callen van een functie veel tijd. Is het dan beter om die functie te verwerken in de main?
Maar als ik het goed begrijp kost het steeds callen van een functie veel tijd. Is het dan beter om die functie te verwerken in de main?
