Algoritmus um Zahl zwischen 1 und 1000 zu finden!

Faithless · Beiträge: 26

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

wulfskin · Verfasst: Do 16.11.06 00:10

BINÄRE SUCHE ist wohl das richtige für dich! Und es ist ganz einfach, dass bekommst du selber hin!

Viel Erfolg,
Hape

_________________
Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.

Coder · Beiträge: 1383 Erhaltene Danke: 1 WinXP D2005 PE

Ich würd es einfach immer durch 2 Teilen.
Das wäre IMHO durschnittlich am effektivsten :gruebel:

Edit// Wow ich hatte sogar recht

*freu*

MfG

DaiweL · Beiträge: 27

markieren

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...

markieren

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

Narses · Verfasst: Do 16.11.06 00:42

Moin!

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

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

wulfskin · Verfasst: 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:

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!

_________________
Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.

Narses · Verfasst: Do 16.11.06 00:47

... ich hab was verpasst... :autsch:

_________________
There are 10 types of people - those who understand binary and those who don´t.

Faithless · Beiträge: 26

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!

Christian S. · Beiträge: 20451 Erhaltene Danke: 2264 Win 10 C# (VS 2019)

Narses hat folgendes geschrieben:

... ich hab was verpasst... :autsch:

Außerdem gehört die Algorithmen-Sparte zu beiden Foren (Delphi und C#)!

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".

DaKirsche · Verfasst: Do 16.11.06 13:53

Also ich würde immer immer den Maxwert halbieren und dann jeweils entweder den höheren Bereich oder den unteren Bereich benutzen und diesen Vorgang ikmmer wiederholen.

Damit grenzt du die Zahl relativ schnell ein.

Ich hatte zumindest so meinen Suchalgorithmus mit c++ realisiert.

_________________
Die simpelsten Fehler sind meist die Schwersten...

TheUnknown · Beiträge: 334

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 · Beiträge: 26

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

Ehemaliges Mitglied Erhaltene Danke: 1

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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme