024
20.07.2002, 11:49 Uhr
virtual
Sexiest Bit alive
(Operator)
|
Hi,
ich hab mal zwei Lösungen zum Wurmrätsel gemacht, die erste guckt nicht auf die Performance, sondern ist eher als Gimmick gedacht:
| C++: |
#include <iostream>
#include <string>
std::string&
replace_all(
std::string& str,
const std::string& search,
const std::string& replace)
{
std::string::size_type diff_len = replace.length()-search.length()+1;
for(std::string::size_type i=str.find(search);
std::string::npos != i;
i=str.find(search, i+diff_len))
{
str.replace(i, search.length(), replace);
}
return str;
}
std::string&
next_generation(
std::string& worm)
{
replace_all(worm, "111", "A");
replace_all(worm, "11", "B");
replace_all(worm, "222", "C");
replace_all(worm, "22", "D");
replace_all(worm, "333", "E");
replace_all(worm, "33", "F");
replace_all(worm, "1", "11");
replace_all(worm, "2", "12");
replace_all(worm, "3", "13");
replace_all(worm, "A", "31");
replace_all(worm, "B", "21");
replace_all(worm, "C", "32");
replace_all(worm, "D", "22");
replace_all(worm, "E", "33");
replace_all(worm, "F", "23");
return worm;
}
int
main()
{
int max_generation;
std::string worm("1");
std::cout << "Bitte max. Generation eingeben: " << flush;
std::cin >> max_generation;
for(int i=1; i<=max_generation; ++i, worm=next_generation(worm))
{
std::cout << "Generation " << i << ": " << worm.length() << endl;
}
}
|
Naja, ohne Worte halt.
Die andere Lösung war schon eher ernst gemeint, kommt aber auch nicht an die Performance von der Lösung von NemoEimi dran (der Unterschied ist deutlich). Ist auch sehr unübersichtlich geworden:
| C++: |
#include <iostream>
#include <vector>
typedef std::vector<int> worm_t;
worm_t&
next_generation(
worm_t& worm)
{
worm_t::size_type current_size = worm.size();
worm_t::size_type expected_size = 0;
worm_t::size_type j = 0;
worm_t::size_type k = 0;
int digit;
while(j<current_size)
{
digit = worm[j];
k = j;
while (digit == worm[j])
{
worm[k] += 10;
++j;
}
expected_size += 2;
}
worm.resize(expected_size);
j = expected_size;
k = current_size;
while (k!=0)
{
if ((digit=worm[k-1])>10)
{
worm[--j] = digit%10;
worm[--j] = digit/10;
if (--k>j) k = j;
}else
--k;
}
return worm;
}
int
main()
{
int max_generation;
worm_t worm;
worm.push_back(1);
std::cout << "Bitte max. Generation eingeben: " << flush;
std::cin >> max_generation;
for(int i=1; i<=max_generation; ++i, worm=next_generation(worm))
{
std::cout << "Generation " << i << ": " << worm.size() << endl;
}
}
|
Sorry Christian, Deien Lösung konnte ich nicht vergleichen, schaut aber gut aus. Ich denke, daß das Format allerdings der Performance killer sein wird.
Schönes Wochenende,
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
Dieser Post wurde am 20.07.2002 um 11:54 Uhr von virtual editiert. |
