Fröhliche Zahlen

Sone schrieb:

template<typename Type>
typename std::enable_if<std::is_integral<Type>::value, bool>::type isHappy(Type initial)
{
    Type next,
         cur  = initial;
    for(;;)
    {
        next = 0;
        while(cur)
        {
            Type mod = cur % 10;
            next += mod * mod;
            cur /= 10;
        }

        if(next == 1)
            return true;
        if(next == initial)
            return false;

        cur = next;
    }
}

Ist das eigentlich so, dass der Zyklus immer mit dem initial Wert endet? Kommt 2 nicht ein den 4er Zyklus?

Sone

Ist das eigentlich so, dass der Zyklus immer mit dem initial Wert endet?

...
Lies bitte den Wikipedia-Artikel.

Kommt 2 nicht ein den 4er Zyklus?

Ich verstehe nicht was du meinst. :xmas2:

Sone schrieb:

Ist das eigentlich so, dass der Zyklus immer mit dem initial Wert endet?

...
Lies bitte den Wikipedia-Artikel.

Habe ich und besser verstanden als du.

Kommt 2 nicht ein den 4er Zyklus?

Ich verstehe nicht was du meinst. :xmas2:

Endlosschleife bei isHappy(2) mit deinem Code.

Sone

SchokoladeMandeln schrieb:

Sone schrieb:

Ist das eigentlich so, dass der Zyklus immer mit dem initial Wert endet?

...
Lies bitte den Wikipedia-Artikel.

Habe ich und besser verstanden als du.

Sry, ich hab zu schnell gelesen.
Ja, du hast Recht. Ich muss aber nur eine Zeile ändern

template<typename Type>
typename std::enable_if<std::is_integral<Type>::value, bool>::type isHappy(Type cur)
{
    Type next;

    for(;;)
    {
        next = 0;
        while(cur)
        {
            Type mod = cur % 10;
            next += mod * mod;
            cur /= 10;
        }

        if(next == 1)
            return true;
        if(next == 4)
            return false;

        cur = next;
    }
}

Und jetzt noch mit Iteratoren!

template<typename T,
         typename = typename std::enable_if<std::is_integral<T>::value>::type>
T isHappy(T n)
{
  for (;;) {
    n = std::sum(make_transform_iterator(digit_iterator(n), [](T t){return t*t;}),
                 make_transform_iterator(digit_iterator(0), [](T t){return t*t;}));
    if (n == 1) return true;
    if (n == 4) return false;
  }
}

Sone

Haha, ja .. wenn man C++11 benutzen darf

Ich habe mir nicht die Mühe gemacht, Deinen Algorithmus, den Du programmiert hast zu verstehen, allerdings habe ich eine Vermutung, was Du versuchst und wie.

Das wird so nicht funktionieren!

Der std::vector von C++ hat eine bestimme Größe und eignet sich nur bedingt, für die Abbildung aller möglichen quadrierten und summierten Ergebnisse, d.h. wenn Du auf einen Vektor an Stelle zahlen2[summen[u]] zugreifst, muss auch gelten: summen[u] < zahlen2.size() . Entweder du vergrößerst Den Vector immer entsprechend, oder Du wählst einen anderen Container. Z.b. zwei std::sets für fröhlich/traurig.

Ausserdem: niemand mag Magic-Numbers:
const unsigned int happy = 1;

Namal

@Furble Wurble, danke. Dass es nicht das Wahre ist, seh ich ein.

Furble Wurble schrieb:

muss auch gelten: summen[u] < zahlen2.size()

Kann ich es nicht einfach durch

for(int u=0;u<summen.size() && summen[u] < zahlen2.size();++u)

vermeiden?

Furble Wurble schrieb:

Ausserdem: niemand mag Magic-Numbers:
const unsigned int happy = 1;

???

@Sonne, jetzt habe ich deinen Code mehr oder weniger verstanden, allerdings ist es ja grad so, dass die schon untersuchten Zahlen dann immer wieder untersucht werden, das möchte ich ja irgendwie vermeiden.

Namal schrieb:

@Sonne, jetzt habe ich deinen Code mehr oder weniger verstanden, allerdings ist es ja grad so, dass die schon untersuchten Zahlen dann immer wieder untersucht werden, das möchte ich ja irgendwie vermeiden.

frag doch werner, ob er dir einen fröhlichen zahlen iterator baut.
http://www.c-plusplus.net/forum/311250

Sone

Furble Wurble schrieb:

Ausserdem: niemand mag Magic-Numbers:
const unsigned int happy = 1;

???

Er meint magische Zahlen.

@Sonne, jetzt habe ich deinen Code mehr oder weniger verstanden, allerdings ist es ja grad so, dass die schon untersuchten Zahlen dann immer wieder untersucht werden, das möchte ich ja irgendwie vermeiden.

premature optimization is the root of all evil

Namal

Ok, noch ein Versuch:

de <iostream> 
#include <vector> 
#include <cmath> 
#include <iomanip> 

using namespace std; 

vector <bool> Sieben (int n){
	vector <bool> z(n,false);

	z[1]=true;

	for(int k=2;k<z.size();++k){

	int sum=0; 

		int d = k;
		while(d){
			int mod = d%10;
			sum +=mod*mod;	
			d/=10;
		}

		if(sum == 1) 
			z[k]=true; 
		if(sum == 4) 
			z[k]= false;

		d=sum;
	}	

return z;
}

void Ausgabe(const vector<bool> &z){ 
     int i=0; 
     for (int k=0;k<z.size();++k){              
         if(z[k]){ 
                 cout<<setw(5)<<k; 
                 ++i; 
                 if(i>9) 
                     { 
                         cout<<'\n'; 
                         i=0; 
                     }       
         } 

     }   
     cout<<'\n'; 
} 

int main(int argc,char *argv[]){

	vector<bool> froh=Sieben(5000);
	Ausgabe(froh);
	return 0;
}

Diesmal werden mir aber nur die Zahlen mit 1 am Anfang ausgegeben :xmas2:
Bin auch blöd, da gehört eine schleife drumrum.

Namal

vector <bool> Sieben (int n){
	vector <bool> z(n,false);

	z[1]=true;
	z[4]=false;

	for(int k=2;k<z.size();++k){
		if(k==4) continue;

		int sum=0; 
		int d = k;
		while(d!=1 || d!=4){	
			while(d){
				int mod = d%10;
				sum +=mod*mod;	
				d/=10;
			}

			if(sum == 1){ 
				z[k]=true; 
			}
			if(sum == 4) 
				z[k]= false;

			d=sum;

		}	
	}	

return z;
}

Kann mir bitte jemand sagen, warum das in einer Endlosschleife endet?

Namal schrieb:

while(d!=1 || d!=4){

Namal

while(d!=1 && d!=4){

So funktioniert es aber auch nicht

Wahrscheinlich ist's Quatsch, aber ich habe mir Deinen ursprünglichen Algorithmus nochmal vorgenommen.
Ich schätze Du hast Dich zu schnell an klein-klein aufgehangen, weil es eigentlich "straight forward" geht.

Könnte so aussehen:

#include <iostream>
#include <vector>
#include <stdexcept>

unsigned int sum_quad(unsigned int n){
  unsigned int sum = 0;
  while(n){
    unsigned int m = n % 10;
    sum += m * m;
    n/=10;
  }
  return sum;
}

void sieve(std::vector<bool>& sieved){
  if(sieved.empty()) return;
  const unsigned int happy_tag   = 1;
  const unsigned int unhappy_tag = 2;
  std::vector<unsigned int> n(1000);  // 1000 ist "aus der Luft gegriffen"
  // einige Werte vorinitialisieren, sonst kein abbruch
  /* assert(5<n.size()); */
  n[0]=unhappy_tag;
  n[1]=happy_tag;
  n[4]=unhappy_tag;

  // hiermit checken wir, bevor wir auf einen arrayindex zugreifen:
  auto bounds = [](unsigned int ix, std::size_t ubound) -> void {
    if(!(ix<ubound)) throw std::range_error("out of bounds error in sieved()");
  };

  for(std::size_t i = 0; i<sieved.size(); ++i){
    // Kandidaten summieren u. quadrieren
    const unsigned int k = sum_quad(i);
    bounds(k, n.size());

    // wie markiert?
    switch(n[k]){
    case happy_tag:
      sieved[i] = true;
      break;
    case unhappy_tag:
      sieved[i] = false;
      break;
      // weder fröhlich noch traurig
    default:
      {
	// folge der summierten/quadrierten Zahlen in sums speichern:
	std::vector<unsigned int> sums={k};
	bool happy = false;
	// summieren/quadrieren, bis wir auf was markiertem landen:
	for(unsigned int j = sum_quad(k);;j=sum_quad(j)){
	  bounds(j, n.size());
	  if(n[j] == happy_tag){
	    sieved[i] = happy = true;
	    break;
	  }
	  if(n[j] == unhappy_tag){
	    sieved[i] = happy = false;
	    break;
	  }
	  sums.push_back(j);
	}
	// die summierten/quadrierten Zahlen in der Menge "aller" Zahlen entspr. markieren:
	for(auto first=sums.begin(), last = sums.end(); first!=last; ++first)
	  n[*first] = happy ? happy_tag : unhappy_tag;
      }
    }
  }
}

int main()
try{
  const unsigned int N = 101;
  std::vector<bool> happy(N);
  sieve(happy);
  for(unsigned int i = 0; i < happy.size(); ++i)
    if(happy[i]) std::cout << i << ' ';
  std::cout << '\n';
 }
 catch(std::exception& ex){
   std::cerr << ex.what() << '\n';
   return -1;
 }

Namal

Das geht garnicht zu kompilieren wegen Zeile 64:

64:15: error: ���first��� does not name a type
64:54: error: expected ���;��� before ���first���
64:54: error: ���first��� was not declared in this scope
64:61: error: ���last��� was not declared in this scope

Du kannst ja den Typen von first explizit hinschreiben:

std::vector<unsigned int>::const_iterator first =...

Allerdings wundert mich das schon, weil ich auto ja mehrfach benutze.
Vielleicht kriegst Du's ja noch kompiliert...

Ansonsten freut Dich vielleicht, dass Dein Algorithmus es wirklich viel schneller ist, als die naive Implementierung...

Namal

Ok, jetzt hab ich's raus. Das Problem lag daran, dass ich erst die Summe in den Vektor gesetzt habe und DANN überprüft habe, ob sie vorkommt. Doh :xmas2:

Jetzt läuft alles :xmas1:

#include <iostream> 
#include <vector> 
#include <iomanip> 

using namespace std; 

vector <bool> Sieben (int n){
	vector <bool> froh(n,false);

	const int istfroh=1;
	const int nichtfroh=2;

	vector <int> markierung(froh.size(),0);

	markierung[0]=nichtfroh;
	markierung[1]=istfroh;
	//markierung[4]=nichtfroh;

	for(int k=2;k<markierung.size();++k){ 

		if(markierung[k]==0){ 

			vector <int> summen;
			int d=k, sum=0; 

			bool schliessewhile = false;
			while(d!=1){  //&& d!=4

				while(d){ 
					int m = d % 10; 
					sum += m * m; 
					d/=10; 
				} 

        /*falls man nicht weiss, dass es nur einen Zyklus fuer nichtfroh gibt*/
				for (int r=0;r<summen.size();++r){  
					if(sum==summen[r]){
						for(int u=0;u<summen.size() && summen[u]<markierung.size();++u) 
							markierung[summen[u]]=nichtfroh; 
						markierung[k]=nichtfroh; 
						schliessewhile=true; 
						break;  
						}
					}

				if (schliessewhile) break;   

				if(markierung[sum]==istfroh){ 
					for(int u=0;u<summen.size() && summen[u]<markierung.size();++u) 
						markierung[summen[u]]=istfroh;   
					markierung[k]=istfroh; 
					break; 
				} 

				if (markierung[sum]==nichtfroh){ 
					for(int u=0;u<summen.size() && summen[u]<markierung.size();++u) 
						markierung[summen[u]]=nichtfroh;   
					markierung[k]=nichtfroh; 
					break; 
				}

				summen.push_back(sum); 
				d=sum; 
        sum=0;

			}

			if(d==istfroh)
				markierung[k]=istfroh;
			//if(d==nichtfroh)
			//	markierung[k]=nichtfroh;

		} 	
	}	  

	for(int k=0;k<markierung.size();++k)
		if(markierung[k]==istfroh) 
			froh[k]=true; 

	return froh;
}

void Ausgabe(const vector<bool> &z){ 
     int i=0; 
     for (int k=0;k<z.size();++k){              
         if(z[k]){ 
                 cout<<setw(5)<<k; 
                 ++i; 
                 if(i>9) 
                     { 
                         cout<<'\n'; 
                         i=0; 
                     }       
         } 

     }   
     cout<<'\n'; 
} 

int main(int argc,char *argv[]){

vector<bool> froh=Sieben(5000);
Ausgabe(froh);
}