Практика программирования (Бейсик, Си, Паскаль)




Поиск - часть 4


  • это число меньше загаданного;
  • это число больше загаданного;
  • это число равно загаданному.

    Оптимальное поведение отгадывающего в точности повторяет схему бинарного поиска. Сначала надо предложить число, расположенное в середине интервала, т. е. N/2. Затем, сузив интервал поиска вдвое, повторить аналогичный маневр. Попадание в цель произойдет не более чем через log2N шагов.

    Приведенные ниже тексты программ реализуют оптимальную тактику отгадывания чисел из диапазона [0,100], затрачивая на это не более 7 шагов. На вопросы программы загадавший должен нажимать клавишу Y или у (в случае положительного ответа) или любую другую клавишу, если вопрос программы не соответствует загаданному числу.

    Программа 4_02.bas

    'Программа угадывания задуманного числа в интервале [0,100]

    DEFINT A-Z

    CLS

    LEFT=0: RIGHT=100:

    DO

    MIDDLE=(LEFT+RIGHT)\2

    PRINT "Задуманное Вами число больше, чем"; MIDDLE; " (Y/N) - ";

    INPUT "",A$

    IF RIGHT-LEFT <= 1 THEN

    IF A$="Y" OR A$="y" THEN

    PRINT "Вы задумали ";RIGHT: END

    ELSE

    PRINT "Вы задумали ";LEFT: END

    END IF

    END IF

    IF A$="Y" OR A$="y" THEN LEFT=MIDDLE+1 ELSE RIGHT=MIDDLE

    LOOP

    END

    Программа 4_02.с

    /* Программа угадывания задуманного числа в интервале [0,100] */

    #include <stdio.h>

    #include <conio.h>

    main ()

    {

    int left=0, right=100, middle, ok;

    char ch;

    clrscr();

    for (;;)

    {

    middle={left+right)/2;

    printf("\n Задуманное Вами число больше, чем % d (Y/N) - ", middle);

    ch=getche();

    if(right-left <= 1)

    if (ch=='Y' || ch == 'y') { ok=right; break; }

    else { ok=left; break;}

    if(ch=='Y' II ch== 'y') left=middle+l;

    else right=middle; }

    printf("\пВы задумали %d",ok); getch(); }

    Программа 4_02.pas

    { Программа угадывания задуманного числа в интервале [0,100] }

    uses Crt;

    var

    ch: char;

    left, right, middle, ok: byte;

    begin

    left:=0;

    right:=100;

    clrscr;

    repeat

    middle := (left + right) div 2;

    write('Задуманное Вами число больше, чем ',middle,' (Y/N) - ');

    ch:=readkey;

    writeln(ch);

    if (right-left <= 1) then

    if (ch='Y') or (ch = 'y') then begin ok:=right;

    break;

    end else begin ok:=left;

    break;

    end; if(ch='Y') or (ch='y') then left := middle + 1

    else right := middle;

    until false;

    writeln('Вы задумали ',ok);

    readln;

    end.




    Содержание  Назад  Вперед