1 Востаннє редагувалося koala (26.09.2021 08:22:37)

Тема: Бінарний пошук числа

Допоможіть ,будь ласка , допописати пронраму для цього завдання .

Плтрібно написати програму пошуку чисел, де програма загадує випадкове значення і сама буде шукати власне випадкове значення . Діапазон значень від 1 до 100 включно . Щоб знайти число, скористайтесь методом розділення інтервалів. Завдяки цьому ви зможете знайти потрібний номер у гіршому випадку за 7 кроків. Поділіть інтервали навпіл, це число буде вашою оцінкою, а потім порівняйте його зі випадковим значенням, щоб дізнатися, в якому інтервалі він знаходиться. Відрегулюйте межі інтервалів і повторюйте, поки не знайдете. Ви можете створити нові змінні для меж інтервалів.

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
 
int main()
{
    srand(time(0));
    int random = rand() % 100 + 1;
    int num;

    while(1) {
        printf("Random:%d\n", );

        if(num>75)
            printf("%d\n", )

        else if(num<50)
            printf("%d\n", )

        else if (num>50) 
            printf("%d\n", )

        else if(num>25)
            printf("%d\n", )

        if (num==random)
            printf("Hotovo!")
    }
}

2

Re: Бінарний пошук числа

"Пронрама" повний брєд, її треба не дописати а написати.
Тут все на стільки погано, що я навіть не знаю з чого почати...
Мабуть треба оце спочатку прочитати.
Потім, хоча б, написати сюди своїми словами як ви думаєте, що має програма робити.

Іще код треба в тег code сувати, у коали про це згадується.

Подякували: MariiaZ1

3

Re: Бінарний пошук числа

Вам треба пам'ятати інтервал - тобто його межі. Проголосіть змінні left і right. Вставте їхнє значенняя по межах - 1 і 100, відповідно. Далі знайдіть середину інтервалу (змінну middle) і порівняйте її з загаданим числом; відповідно до результатів порівняння змініть інтервал (тобто вставте або left, або right на середину), доки не знайдете число.
Теги code я вам додам, але далі самостійно.

Подякували: MariiaZ1

4

Re: Бінарний пошук числа

Chemist-i, та нормальний код для людини, що досі лише лінійний код писала і ще в змінних плаває. Спроба є, проблема зрозуміла.

Подякували: MariiaZ1

5

Re: Бінарний пошук числа

Мова програмування не була вказана. З include'ів я зробив висновок, що має бути C.


Ці значення можна користати як інформацію про результат порівняння.

// comparison_result.h

#ifndef COMPARISON_RESULT_H
#define COMPARISON_RESULT_H

typedef enum {
    Less    = -1,
    Equals  =  0,
    Greater = +1
} comparison_result;

#endif

Ця функція приймає функцію (аргумент) і повертає функцію (результат). Функція-аргумент генерує int, який зберігається для майбутніх порівнянь. Функція-реультат дозволяє порівняти збережене значення з тим, яке передав користувач, скільки завгодно разів.

// container.h

#ifndef CONTAINER_H
#define CONTAINER_H

#include "comparison_result.h"

comparison_result (*container(int (*const generator)(void)))(int const);

#endif

В такий спосіб я намагався зховати сам int і дати користувачу тільки container для порівняння.

// container.c

#include "comparison_result.h"
#include "container.h"

static int storedValue = 0;

comparison_result compare(int const l, int const r) {
    return l > r ? Greater : l < r ? Less : Equals;
}
comparison_result compare_stored_value_with(int const value) {
    return compare(storedValue, value);
}
comparison_result (*container(int (*const generator)(void)))(int const) {
    storedValue = generator();
    return compare_stored_value_with;
}

Приклад користання. Містить функцію, яка псевдовипадково генерує число, і функцію, яка знаходить це число (без доступу до самого числа).

// main.c

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#include "comparison_result.h"
#include "container.h"

int get_random_value(void);
int find_value(comparison_result (*const)(int const));

int main() {
    comparison_result (*c)(int const) = container(get_random_value);
    int value = find_value(c);
    printf_s("%i\r\n", value);
    return 0;
}
// Return integer from range [0, 127]
int get_random_value(void) {
    srand(time(0));
    int value = rand();
    value ^= value >> 0x08; // optional
    value ^= value >> 0x10; // optional
    value &= (-1 << 7) ^ -1;
    return value;
}
// Return positive integer mined from container
int find_value(comparison_result (*const container)(int const)) {
    int bit = 0x80;
    int value = 0;
    comparison_result r;
    do {
        r = container(value | bit);
        if(r != Less) value |= bit;
        bit >>= 1;
    } while(bit > 0 && r != Equals);
    return value;
}

На практиці користувати це майже не можливо, бо користувач захоче мати більше ніж 1 container, а static int тут тільки 1.

Пропонуйте свої варіанти. Особливо цікаво чи існує елегантне рішення цієї задачі на C.

Подякували: ch0r_t, MariiaZ, ReAl3

6 Востаннє редагувалося ch0r_t (01.10.2021 09:01:04)

Re: Бінарний пошук числа

Використав метод каменюки і дубинки, розроблений мною колись.

#include <stdio.h>
#include <stdlib.h>

int main(){
    srand(42); // або без різниці.
    int x = rand() % 100 + 1;
    printf("X is =%d\n", x);
    for(int i = 0, n = 100, t=0; i <= 16; ++i){
        if(n == x){ printf("____> Here: %d\niter = %d", n, i); break;}
        if(x == n-1){--n; continue;} else if(x == n+1){++n; continue;}
        if((t+n) % 2 != 0){n += i-1 ? i%2 : 0;}
        if(n > x){ t = n; n /= 2;} else {n = (( t+n ) / 2);}
    }
    return 0;
}
Подякували: MariiaZ1

7 Востаннє редагувалося wander (28.09.2021 22:53:58)

Re: Бінарний пошук числа

leofun01, дивлячись на ваш код, мені в голову вдарила цікава ідея, спробувати написати ваш код під С++20 з їхніми новими компараторами, вийшло доволі непогано  :D

Прихований текст

Протестувати можна тут.

integer.hpp
#pragma once

#include <compare>
#include <ostream>

struct [[nodiscard]] Integer final {
    constexpr Integer(int const value) : value_{value}
    { }

    friend constexpr auto operator<=>(Integer, Integer) noexcept = default;
    friend constexpr bool operator== (Integer, Integer) noexcept = default;

    friend constexpr Integer operator| (Integer const, Integer const) noexcept;
    friend constexpr Integer operator<<(Integer const, Integer const) noexcept;
    friend constexpr Integer operator>>(Integer const, Integer const) noexcept;
    
    friend std::ostream& operator<<(std::ostream&, Integer const);

private:
    template <int, int> friend struct Integer_generator;
    
    int value_;
};

constexpr Integer operator|(Integer const lhs, Integer const rhs) noexcept {
    return {lhs.value_ | rhs.value_};
}

constexpr Integer operator<<(Integer const lhs, Integer const rhs) noexcept {
    return {lhs.value_ << rhs.value_};
}

constexpr Integer operator>>(Integer const lhs, Integer const rhs) noexcept {
    return {lhs.value_ >> rhs.value_};
}

std::ostream& operator<<(std::ostream& os, Integer const v) {
    os << v.value_;
    return os;
}
integer_generator.hpp
#pragma once

#include <cstdlib>
#include <ctime>

template <int l, int r>
struct [[nodiscard]] Integer_generator final {
    static constexpr Integer min{l};
    static constexpr Integer max{r};

    Integer operator()() const noexcept {
        [[maybe_unused]] static bool const seed = (std::srand(std::time(0)), true);
        return {rand() % max.value_ + min.value_};
    }
};
main.cpp
#include <iostream>
#include <utility>

#include "integer.hpp"
#include "integer_generator.hpp"

std::pair<Integer, std::size_t> find(Integer const v) noexcept {
    Integer bit   = 0x80;
    Integer value = 0;
    
    auto i = std::size_t{0};
    auto r = std::compare_three_way_result_t<Integer>::less;
    for (; i < 7 && r != decltype(r)::equal; i++) {
        if (r = v <=> (value | bit); r >= 0) value = value | bit;
        bit = bit >> 1;
    }
    return {value, i};
}

int main() {
    Integer random_value = Integer_generator</* min: */ 1, /* max: */ 127>{}();
    auto [result, it]    = find(random_value);
    
    std::cout << "Generated random value = " << random_value << std::endl;
    std::cout << "Result value = " << result << ", iterations: " << it << std::endl;
}
leofun01 написав:

Особливо цікаво чи існує елегантне рішення цієї задачі на C.

Дивлячись, що для вас означає "елегантне " :)
Але, я б для початку точно позбувся тих страшних вказівників на ф-ї (привіт typedef).

Подякували: leofun011

8

Re: Бінарний пошук числа

leofun01 написав:
// Return positive integer mined from container
int find_value(comparison_result (*const container)(int const)) {
    int bit = 0x80;
    int value = 0;
    comparison_result r;
    do {
        r = container(value | bit);
        if(r != Less) value |= bit;
        bit >>= 1;
    } while(bit > 0 && r != Equals);
    return value;
}

Ця функція, точніше, її ядро без компаратора, для 8- та 12-бітного варіантів, випускалася колись у вигляді мікросхеми :-)
Не лише для розсипушних SAR ADC.

Подякували: leofun011

9

Re: Бінарний пошук числа

tchort написав:

Використав метод каменюки і дубинки, розроблений мною колись.

#include <stdio.h>
#include <stdlib.h>

int main(){
    srand(42); // або без різниці.
    int x = rand() % 100 + 1;
    printf("X is =%d\n", x);
    for(int i = 0, n = 100, t; i <= 16; ++i){
        if(n == x){ printf("____> Here: %d\niter = %d", n, i); break;}
        if(x == n-1){--n; continue;} else if(x == n+1){++n; continue;}
        if((t+n) % 2 != 0){n += i-1 ? i%2 : 0;}
        if(n > x){ t = n; n /= 2;} else {n = (( t+n ) / 2);}
    }
    return 0;
}

Ви не ініціалізуєте t. Загалом нічого страшного, але може бути одна абсурдна операція.

Подякували: ch0r_t1

10

Re: Бінарний пошук числа

Прихований текст
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LOWER 1
#define UPPER 100

int main(void) {
    srand(time(NULL));
    int x = rand() % UPPER + LOWER;
    printf("X = %d\n", x);
    int left, right;
    for(left = LOWER, right = UPPER; left < right;)
    {
        int guess = (left+right) / 2;
        printf("left =\t%d, right =\t%d, guess = %d\n", left, right, guess);
        if(guess < x)
            left = guess;
        else if(guess> x)
            right = guess;
        else
            left = right = guess;
    }
    printf("guess = %d\n", left);
    return 0;
}
Подякували: leofun011

11

Re: Бінарний пошук числа

wander написав:

код під С++20 з їхніми новими компараторами

Вау.. Нарешті комітет прийняв до уваги надлишковість тих операторів.

cppreference.com написав:

(removed in C++20)

wander написав:

я б для початку точно позбувся тих страшних вказівників на ф-ї (привіт typedef).

Спочатку я писав код з typedef'ами, але потім вирішив їх прибрати, щоб показати що так теж можна.
Записувати вказівники на функції через typedef - дуже поширена практика. А як записати функцію, яка повертає вказівник на функцію, без typedef - інформація, яка погано ґуґлиться, і багато лінків ведуть на приклади з typedef. Від цього в новачка складається враження, що існує тільки один спосіб (з typedef), а до іншого він може не дійти.

wander написав:
leofun01 написав:

Особливо цікаво чи існує елегантне рішення цієї задачі на C.

Дивлячись, що для вас означає "елегантне " :)

  1. Для мене цікавими є рішення саме мовою C. Рішення C++ не є цікавими через існування вбудованої енкапсуляції і лямбда виразів.

  2. Значення, яке користувач має знайти, треба зберігати (а може й не треба) так, щоб користувач не мав доступу до самого значення.

  3. Користувачу треба дати інструмент, який дозволить отримати інформацію про відношення шуканого і того, яке подав користувач. Цей пункт - не проблема.

12

Re: Бінарний пошук числа

leofun01 написав:

Значення, яке користувач має знайти, треба зберігати (а може й не треба) так, щоб користувач не мав доступу до самого значення.
Користувачу треба дати інструмент, який дозволить отримати інформацію про відношення шуканого і того, яке подав користувач. Цей пункт - не проблема.

А в чому тоді проблема?

P.S. -- щодо 2-го пункту, то в мене така практика викликає деякі сумніви :)

13

Re: Бінарний пошук числа

wander написав:

А в чому тоді проблема?

Проблема в тому що запропоноване мною рішення нікуди не годиться, бо отаке

int main() {
    comparison_result (*c1)(int const) = container(get_random_value);
    comparison_result (*c2)(int const) = container(get_random_value);
    int v1 = find_value(c1);
    int v2 = find_value(c2);
    printf_s(" v1 = %i\r\n v2 = %i\r\n", v1, v2);
    return 0;
}

на виході дає 2 одинакові значення, а це не є ок.

14 Востаннє редагувалося wander (04.10.2021 03:05:42)

Re: Бінарний пошук числа

leofun01 написав:

Проблема в тому що запропоноване мною рішення нікуди не годиться

Гм, може я чого не розумію, але я не бачу таких перешкод, щоб цю проблему не можна було вирішити.