Entwickler-Ecke :: Thema anzeigen - Algoritmus um Zahl zwischen 1 und 1000 zu finden!

Faithless - Mi 15.11.06 23:52
Titel: Algoritmus um Zahl zwischen 1 und 1000 zu finden!

Moin Leute!

Hab eine kleines Problem, ich bin informatikstudent, und unser lehrer hat uns eine aufgabe gestellt, und zwar hat er in unix, einen kleinen "ratespielserver" geschrieben, dieser server "denkt" sich eine zahl aus und jeder user schickt sinen Tipp hin, und bekommt entweder die Antwort, kleiner, größer oder Treffer!

So unsere Aufgabe ist es nun, ein programm zu schreiben, in der Linux shell das diese zahl möglichst, schnell findet!

So ich habe mir jetzt überleget, die tausend durch vier zu teilen, und erstmal 250, 500 usw. an den server zu senden, damit ich mittels der größer, bzw kleiner antwort den block ermitteln kann in dem die zahl vorhanden ist, so hätte ich im schlimmstenfall 250 versuche bis ich nen treffer lande, also nach meiner "Brutforce" methode!

Hat da einer von euch vielleicht ne bessere idee, wies schneller und effektiver geht, am besten wärs wenn ihr vielleicht nen beispielcode, aus c oder delphi hättet!

Jetzt shcon ma vielen dank!

Let the good times roll

DaiweL - Do 16.11.06 00:18

C#-Quelltext

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:

#include <stdio.h>
int isZahl(int i) {
  int Zahl=322;
  if(Zahl == i) return -1;
  if(Zahl >  i) return 1;
  if(Zahl <  i) return 0;
}

int main() {
  int max=1000;
  int min=1;
  int i=max/2;
  int found=0;
  while(found!=-1) {
    found=isZahl(i);
    if(found==1) {
      min=i;
      i=i+(max-min)/2;
    }else if(found==0) {
      max=i;
      i=i-(max-min)/2;
    }
  }
  printf("Zahl = %d",i);
  return 0;
}

die Funktion isZahl simuliert das ratesspiel deines lehrers:
gefunden = -1
grösser = 1
kleiner = 0

oder mit zufallsgenerator, manchmal schneller...

C#-Quelltext

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:

#include <stdio.h>
#include <stdlib.h>
int isZahl(int i) {
  int Zahl=322;
  if(Zahl == i) return -1;
  if(Zahl >  i) return 1;
  if(Zahl <  i) return 0;
}

int main() {
  int max=1000;
  int min=1;
  int i=1000/2;
  int found=0;
  srand(time(0));
  do {
    if(found==1) {
      min=i;
      i=rand()%(max-min)+min;
    }else if(found==0) {
      max=i;
      i=rand()%(max-min)+min;
    }
    found=isZahl(i);
  } while(found!=-1);
  printf("Zahl = %d",i);
  return 0;
}

mfg aus Luxemburg

wulfskin - Do 16.11.06 00:46

Narses hat folgendes geschrieben:

Moin!

Hab ich was verpasst, oder ist das hier doch noch das Delphi-Forum? :gruebel: :mrgreen:

cu
Narses

Faithless hat folgendes geschrieben:

Hat da einer von euch vielleicht ne bessere idee, wies schneller und effektiver geht, am besten wärs wenn ihr vielleicht nen beispielcode, aus c oder delphi hättet!

;)

Faithless - Do 16.11.06 09:15

Hey,

super danke jungs, ich werds mal versuchen das umzu setzen was ihr gesagt habt, das problem ist hierbei nur das die unixshell über eingeschränkete rechenmittel verfügt, naja wir werden´s schon hinkriegen!

Und wenn wir gewonnen haben, dann teilen wir die Tüte Gummibärechen mit euch!

So ich geh jetzt mal schön brav in die FH

Vielen dank nochmal!

TheUnknown - Do 16.11.06 14:43

Das ist auch tatsächlich die schnellste Methode (also der Logik nach), Kirsche. Fragt sich dann nur noch, welche/r Sprache/Compiler das in den schnellsten Code setzt, damit die CPU das am perfektesten errechnen kann.

Aber ich frage mich, wiiieeeee schnell es sein muss. Sogar ein 486er unter Win95 und mit Delphi-Programm kriegt das in einer Sekunde, wenn nicht noch weit darunter hin. Will der Prof also nur einen möglichst technisch optimieren Code (also soz. die "Ehre des Proggers wecken"), der den Algorithmus umsetzt oder will der Prof generell eine Lösung für das Problem, egal, wie schnell die ist, Hauptsache, die führt zum Ziel?

Denn den wohl schnellsten Rechenweg haste hier ja jetzt stehen. Fehlt nur noch der kompakteste Algo und der beste Compiler dafür.

Faithless - Do 16.11.06 15:52

Ja, was ihr geschreiben habt, das ist ja die intervall halbierungsmethode, also wenn das wirklich das schenlleste ist, dann werd ich den coden, das ist ja nicht unbedingt schwer!

Es ist gar kein compiler, das ganze wird in der Unix shell geschreiben, so zu sagen ein batchprogramm wir benutzen dazu den VI editor!

Also dem prof ist es grundsätzlich egal wie effektiv der algo ist, er will nru das jeder ein programm schreibt das funktioniert und die zahl findet!

Nur ich bin ein kliner perfektionist, udn wollte es gleich richtig machen, um möglichst schnell zu sein! Aber akzeptieren würde er im erauch die bruteforce methode die einfach alle zahlen von 0 bis 1000 durchrattert!

Aber vielen dank für eure tipps

Delete - Do 16.11.06 23:53

sali miteinand,

jetzt will ich auch mal meinen senf mit dazugeben, auch wenn das problem schon längst gelöst ist

a) das ist ein typisches beispiel für ein bi-selektionsverfahren [ich denke daher will dein prof auf das thema algo. raus ;-)]
b) tja nares, delphi spricht halt auch C und C++ ;-)
c) zum bogo von DaiweL, vergiss es, bringt wirklich keinen vorteil :-)

see you

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!