Programmstruktur

drakon

SeppJ schrieb:

Die beiden naheliegenden Lösungen dafür sind eine Schleife oder eine Rekursion.

Das Problem riecht förmlich nach Rekursion. Ich würd das einfach mal der Eleganz wegen rekursiv definieren.

SeppJ

drakon schrieb:

SeppJ schrieb:

Die beiden naheliegenden Lösungen dafür sind eine Schleife oder eine Rekursion.

Das Problem riecht förmlich nach Rekursion. Ich würd das einfach mal der Eleganz wegen rekursiv definieren.

Aber prinzipiell ist die Rekursion unnötig, da man nur einen einzigen Ast entlangläuft. Ich hätte daher eher die Schleife gewählt.

Interessant wäre auch eine Template-Metaprogrammierungslösung, die einen für jeden Intervall eine passende Funktion erzeugt. Das entspräche zwar effektiv der Lösung mit den 100 switches, aber interessant wäre das trotzdem mal zu sehen. Falls mir am Wochenende mal langweilig ist, programmier ich das mal, falls es noch kein anderer bis dahin gemacht hat.

drakon

SeppJ schrieb:

drakon schrieb:

SeppJ schrieb:

Die beiden naheliegenden Lösungen dafür sind eine Schleife oder eine Rekursion.

Das Problem riecht förmlich nach Rekursion. Ich würd das einfach mal der Eleganz wegen rekursiv definieren.

Aber prinzipiell ist die Rekursion unnötig, da man nur einen einzigen Ast entlangläuft. Ich hätte daher eher die Schleife gewählt.

Interessant wäre auch eine Template-Metaprogrammierungslösung, die einen für jeden Intervall eine passende Funktion erzeugt. Das entspräche zwar effektiv der Lösung mit den 100 switches, aber interessant wäre das trotzdem mal zu sehen. Falls mir am Wochenende mal langweilig ist, programmier ich das mal, falls es noch kein anderer bis dahin gemacht hat.

Ja, unnötig, aber trotzdem elegant. Wie auch die Meta Version.

Das eine Schleife das Mittel der Wahl ist, wenn es ernst gilt, ist klar, aber man darf ja auch verschiedene Ansätze probieren.

volkard

drakon schrieb:

Das Problem riecht förmlich nach Rekursion. Ich würd das einfach mal der Eleganz wegen rekursiv definieren.

Meine Nase ist verstopft.

for(;;){
  int m=(u+o)/2;
  while(int c=compare(m)){
    if(c>0)
      u=m+1;
    else
      o=m-1;
  }
  return m;
}

int m=(u+o)/2;
if(int c=compare(m)){
  if(c>0)
    return rek(m+1,o);
  else
    return rek(u,m-1);
}
else
  return m;

drakon

Hmm. Hab mir das eleganter vorgestellt.
Naja. Jetzt fehlt ja nur noch die Metaversion.

Nexus

drakon schrieb:

Naja. Jetzt fehlt ja nur noch die Metaversion.

Jetzt, wo die rekursive Variante bekannt ist, sollte man mit Metaprogrammierung mehr oder weniger analog vorgehen können.

drakon

Nexus schrieb:

drakon schrieb:

Naja. Jetzt fehlt ja nur noch die Metaversion.

Jetzt, wo die rekursive Variante bekannt ist, sollte man mit Metaprogrammierung mehr oder weniger analog vorgehen können.

Klar. Aber das überlasse ich mal SeppJ oder allenfalls dem TO, wenn er schneller ist.

SeppJ

#include <iostream>

const int min = 1;
const int max = 100;

template<int, int> struct question;    // Must be a class, because function template partial specialization is not allowed

template<int value> struct question<value,value>
{
  static void ask()
  {
    std::cout<<"The answer is "<<value<<std::endl;
  }
};

template<int lower, int upper> struct question
{
  static void ask()
  {
    const int middle=(lower+upper)/2;
    std::cout<<lower<<" "<<upper<<std::endl;
    std::cout<<"Is the answer greater than "<<middle<<"?"<<std::endl;
    bool answer;
    std::cin >> answer;
    if (answer) question<middle+1,upper>::ask();
    else question<lower,middle>::ask();
  }
};

int main ()
{
  question<min,max>::ask();
}

Compiliert auch ordentlich lange, bei mir fast 1 s für 1-100. Für 1-1000 sogar über 5 s.

edit: Und das Programm kommt natürlich mit log2(100)=6.64 Fragen aus. Ok, sagen wir maximal 7 .

edit2: An den Threadersteller: Nimm nicht diese Lösung. Dies ist ein C++-Programmiererscherz und nicht praxistauglich. Orientier dich an dem was volkard geschreiben hat.

drakon

MAX2.0

Hi Leute,

vielen Dank für eure zahlreichen Antworten, ich kann es morgen leider erst detailliert durchgehen, merke aber schon dass ich genau das von euch bekommen habe was ich suche. vielen vielen dank

volkard

SeppJ schrieb:

An den Threadersteller: Nimm nicht diese Lösung. Dies ist ein C++-Programmiererscherz und nicht praxistauglich.

Schön gesagt. Ob Marc++us uns für diesen Satz unten einen Button baut?

MAX2.0

An volkard:

for(;;){
  int m=(u+o)/2;
  while(int c=compare(m)){
    if(c>0)
      u=m+1;
    else
      o=m-1;
  }
  return m;
}

int m=(u+o)/2;
if(int c=compare(m)){
  if(c>0)
    return rek(m+1,o);
  else
    return rek(u,m-1);
}
else
  return m;

Gehören die beiden Algorithmen zusammen? wäre dir sehr dankbar, wenn du mich durch deinen gedankengang führen könntest. (rekursion ist mir leider noch völlig unbekannt... )

also im 1.) nutzt du eine for-schleife (was müsste in den kriterien stehen??) in der praktisch steht, dass m=(u+o)/2 ist, sprich das intervall halbiert. doch was steckt hinter der while schleife und warum wird m erst in der for-schleife deklariert ??

lg max