zu doof dafür!

Spliffy85

Hi Leute,
könnt ihr mir vllt einen Tipp geben, bin immer noch anfänger und steh voll auf dem schlauch.
ich soll ein programm schreiben, dass die zahlen von 1 bis 250 ausgibt, weder durch 7 teilbar noch die ziffer 7 beinhalten. hab scho was zambracht. aber der rest fehlt irgendwie ^^ hilfe! danke

#include <stdio.h>

void main()
{
    int i;

	while(i!=251)
	{
		if(i%7==0)
			i++;

		else
		{
			printf("%i\t",i);
			i++;
		}
	}
}

wie kann ich aber die ziffern mit 7 rausfiltern?!

mfg

mcr

Dann wandel doch die Zahl mit sprintf() in einen String um und überprüfe jede
Ziffer:

int enthaelt_sieben(int zahl) {
    char buf[128];
    int i;

    sprintf(buf, "%s", zahl);

    for (i=0; i<..; ++i) {
        ...
    }

    return 0;
}

Gruß mcr

EDIT: ein ziemlich blöder Name für einen Thread.

pointercrash**

Spliffy, zuerst solltest Du Deinen Int initialisieren, z.B.

int i = 1;

Ist sonst eher Zufall, wenn das läuft.

mcr schrieb:

Dann wandel doch die Zahl mit sprintf() in einen String um und

Und das ist 'ne Performance- Katastrophe, die zwar läuft, aber unschön ist.
Besser so durch fortlaufende Division wie beim Zahlenumwandeln:

173 / 10 = 17 Rest 3 // ist 3 == 7? nöh
17 / 10 = 1 Rest 7 // ist 7 == 7? yep, ausgeben :D

Anderenfalls müßte das in einen String geschüttet werden und im String ausgezählt und dann womöglich nochmal umgerechnet zur Ausgabe.
Alles klar?

Swordfish

pointercrash() schrieb:

Besser so durch fortlaufende Division wie beim Zahlenumwandeln:
173 / 10 = 17 Rest 3 // ist 3 == 7? nöh
17 / 10 = 1 Rest 7 // ist 7 == 7? yep, ausgeben :D

Nö, eben dann nicht ausgeben...

pointercrash() schrieb:

Anderenfalls müßte das in einen String geschüttet werden und im String ausgezählt und dann womöglich nochmal umgerechnet zur Ausgabe.

Nö, einen string wandle ich (ich zumindest!!) nicht mehr in einen integer um, um ihn auszugeben... gute Besserung!
[edit]BTW: Wie denkst du, außer durch sukkzesives Dividieren durch die Basis, wird ein integer in einen String umgerechnet? Der Mehraufwand für diese Methode dürfte sich also in grenzen halten.[/edit]

greetz, Swordfish

BorisDieKlinge

#include <stdio.h>

void main(){
bool seven=false;
	for(long i=0; i< 251 ; i++){

//sieben enthalten?
		for(long buf= i; buf>0; buf/=10){
			if(buf%10==7)
				seven=true;			
		}
//wenn sieben nicht enthalte, und nicht durch 7 teilbar dann ausgeben
		if(i%7!=0 && !seven)
			printf("%i\n",i);

		seven=false;
	}
}

pointercrash**

Swordfish schrieb:

Nö, eben dann nicht ausgeben...

Jaja, Du hast ja recht ...

Swordfish schrieb:

Nö, einen string wandle ich (ich zumindest!!) nicht mehr in einen integer um, um ihn auszugeben... gute Besserung!

Natürlich nicht, aber beim Ausgeben wandelst Du den Int entweder per printf nochmal um, oder Du gibst den String an printf weiter. Auf jeden Fall konvertierst Du JEDE Zahl in einen String und durchsuchst JEDEN String. Wenn das mal kein unnötiger Verbrauch von CPU- Time ist

Swordfish schrieb:

BTW: Wie denkst du, außer durch sukkzesives Dividieren durch die Basis, wird ein integer in einen String umgerechnet? Der Mehraufwand für diese Methode dürfte sich also in grenzen halten.

Unsinn . Mit der Stringmethode wandelst Du alle Zahlen vollständig um und durchsuchst dann auch noch den String . Schau Dir Boris' Lösung mit 'nem Runtime- Profiler an und versuch', mit 'ner Stringsuche in diese Speed- Dimension zu kommen.

@Boris
Yep, so war's gedacht, aber eigentlich ist das hier nicht das fröhliche Hausaufgabenstudio So hast Du Spliffy um den Spaß gebracht, das selbst zu lösen

BorisDieKlinge

@poinercrash: Ich weis, aber wenn er schlau ist, wird er den code nicht so seinem dozent /lehrer präsentieren, weil er wahrscheinlich nicht versteht was der code genau macht.. und das wird er sicher gefragt.. wenn er mal versteht was der code macht hat er auc hwas gelernt;)

pointercrash**

BorisDieKlinge schrieb:

wenn er mal versteht was der code macht hat er auc hwas gelernt;)

Und als Fleißaufgabe kann er die for- Schleife mit buf = 0 verlassen, wenn seven true ist Dann gibt's noch ein Quentchen mehr Speed

BorisDieKlinge

das stimmt, aber dann muss ich die bedingung umklammern.. wäre ne zeile mehr;)

CStoll

BorisDieKlinge schrieb:

das stimmt, aber dann muss ich die bedingung umklammern.. wäre ne zeile mehr;)

Wozu? Es gibt doch den Komma-Operator ("seven=true,buf=0;" geht als eine Anweisung durch)

BorisDieKlinge

stimmt, aber so:

for(long buf=i; !seven && buf>0; buf/10){..}

pointercrash**

BorisDieKlinge schrieb:

stimmt, aber so:

for(long buf=i; !seven && buf>0; buf/10){..}

Da führt er aber den Vergleich auf seven unnötigerweise bei jedem Schleifendurchgang durch (full evaluation), wenn Optimierung zugelassen, gehts meist links nach rechts. Beim Disassemblieren habe ich im for() zwei Vergleiche mehr drin stehen als bei der Lösung von CStoll.
Schlage ihn für den heutigen "Performance- King" vor

Spliffy85

hey,
danke für eure hilfe und große resonanz. anscheinend hab ich da ein weitläufiges thema angestoßen!;)

und das nächste mal nehm ich auch einen treffenderen betreff!;)

pointercrash**

Jetzt hat's mich doch noch gejuckt und ich hab's noch auf einem M16C- Emulator mit 4 Varianten durchgebencht:

V1 - Boris' Urcode ohne for- Abbruch
V2 - CStoll Einzeiler- Ergänzung
V3 - Boris' Abbruchergänzung mit (buf>0) && (!seven)
V4 - Boris' Abbruchergänzung mit (!seven) && (buf>0)

Die Laufweite bis 251 ergibt auf den Hunderter gerundet folgende Ergebnisse:

V2 mit 65'100 Zyklen
V1 mit 67'500 Zyklen
V3 mit 68'100 Zyklen
V4 mit 68'200 Zyklen

Also schmerzt der zusätzliche Vergleich doch ziemlich und man kann durch günstige Anordnung sogar noch ein bißchen was tun. Immerhin liegen zwischen V2 und V4 etwa 5% Unterschied. Überraschend, daß sogar kein vorzeitiger Abbruch schneller ist, als die zusätzliche Kondition im for().
Das hat mich gewundert , also habe ich das Sieb bis 65'000 laufen lassen, dabei kommt heraus:

V2 mit 23,6 Mio Zyklen
V3 mit 24,9 Mio Zyklen
V4 mit 25,1 Mio Zyklen
V1 mit 27,3 Mio Zyklen

Also spielt mit zunehmender Stellenzahl auch der unglücklich implementierte vorzeitige Abbruch seine Stärken aus ;). Zwischen der schwächsten und der stärksten Variante liegen so grob 15%, man schrumpft (über den Daumen skaliert) eine 3 GHz- Kiste auf eine 2,55 GHz- Maschine.
Bei der Umwandlung in einen String (ich habe noch nicht einmal eine Zeichensuche implementiert), wobei der erste for()- Block durch ein

dummy = sprintf( string, "%-5d", i);

ersetzt wurde, kamen

[b]Version Swordfish[/b] 134,3 Mio Zyklen

heraus. Das sind nur noch 17% der möglichen Performance oder der 3 GHZ- Rechner wird zur 500 MHz- Uralt- Gurke.
Was ich damit sagen will: Das war jetzt exemplarisch, aber diese Performance holt auch ein besser optimierendes Compiler/Prozessor- Gespann nicht zurück.

Solange Opas mit Hut im Mercel 500 SEC am Sonntag mit 40 km/h auf der Landstraße genausowenig automatisch den Führerschein verlieren, wie Swordfish die Lizenz zum Coden wird Corel Draw wohl immer lahm bleiben. :p

@swordfish Ist Dir denn gar nicht klar, was bei der Formatstringauswertung alles passiert? Dann zurück auf "Los" und ziehen Sie keine 200 EUR ein!

pointercrash() schrieb:

Solange Opas mit Hut im Mercel 500 SEC am Sonntag mit 40 km/h auf der Landstraße genausowenig automatisch den Führerschein verlieren, wie Swordfish die Lizenz zum Coden wird Corel Draw wohl immer lahm bleiben. :p

das sehe ich ähnlich. pointercrash, du bist mir definitiv sympathisch.

Th

Ich hätte noch eine kleine Optimierung:

seven = false;
for(long buf=i; buf>0; buf/=10)
{
   if(buf%10==7)
   {
      seven=true;
      break;
   }
}

Erspart zumindestens einen weiteren Vergleich...

pointercrash**

Th schrieb:

Erspart zumindestens einen weiteren Vergleich...

Richtig, um es genau anzugeben:

V Th 22,8 Mio Zyklen bei 65000 Durchläufen

, das sind nochmal etwa 3% gespart. Die Performance- Krone wird weitergereicht!

Swordfish

@pointercrash(): ich habs bald darauf selbst geschnallt - Meine Lizenz behalt' ich :p

greetz, Swordfish

Th schrieb:

Ich hätte noch eine kleine Optimierung:
seven = false;
for(long buf=i; buf>0; buf/=10)
{
   if(buf%10==7)
   {
      seven=true;
      break;
   }
}
Erspart zumindestens einen weiteren Vergleich...

schmeiss noch das geteilt und den modulo-raus, dann könnte es noch schneller sein.

BorisDieKlinge

@speed-freak: schmeiss den Motor- zylinderkopf aus dem auto dann is er leichter..

BorisDieKlinge schrieb:

@speed-freak: schmeiss den Motor- zylinderkopf aus dem auto dann is er leichter..

mit so'nem dummen kommentar hab ich schon gerechnet^^
http://blogs.msdn.com/devdev/archive/2005/12/12/502980.aspx