Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Угадай число - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Частица движется случайно. http://www.cyberforum.ru/cpp/thread61260.html
1.Определить есть ли среди первых трех цифр из дробной части заданного положительного вещественного числа цифра 0 помоги плиииз.... такая тема в паскале уже есть...но нужно в си/++...
C++ Две задачи. Задача1. Составить описание класса для определения одномерных массивов строк фиксированной длины. Предусмотреть возможность обращения к отдельным строкам массива по индексам, конртоль выхода за... http://www.cyberforum.ru/cpp/thread61049.html
Работа с файлами (до делать програмку) C++
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream.h> #define MAX 100 struct chit { char fio ; char adres ; char telefon ; int godRojd ;
C++ screenmate: SetWindowRgn - не всегда меняет форму окна
Решил разобраться с устройством Скринмейтов (программок бегающих по экрану:)). Долго мучился с разрезанием картинки и т.д. (С++ знаю не очень...), но тем не менее добился кое-каких результатов....
C++ Быки и коровы http://www.cyberforum.ru/cpp/thread60712.html
Доброе время суток. Пользователь загадывает число из 4 цифр, каждая из которых от 1 до 6, причем все цифры различны. Разработать алгоритм, который угадывает число по следующим правилам: выводится...
C++ Вопрос о типах данных С++ Всем привет! У меня путаница вышла со всем этим разнообразием типов данных в С++. Вообще, тип long double должен занимать 3 машинных слова (или 12 байт). Но вот когда я пишу : #include... подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.11.2009, 13:53
Цитата Сообщение от odip Посмотреть сообщение
Я вот думаю как доказать что этот алгоритм оптимальный.
А для чего (или для кого доказывать). Для меня очевидно, что твой алгоритм оптимальный (по крайней мере с моим).
Даже вот эти выкладки:
Цитата Сообщение от odip Посмотреть сообщение
Из алгоритма ясно, что на каждом шаге мы максимально уменьшаем число возможных комбинаций. То есть любое наше действие и так оптимально.
Например начало.
Изначально у нас N вариантов ответа.
Первый шаг: делится ли n на 2.
При ответе ДА мы получаем N/2 вариантов.
При ответе НЕТ мы получаем N/2 вариантов.
Если же спросить что-нибудь другое, например делится ли наше число на 3.
При ответе ДА мы получаем N/3 вариантов.
При ответе НЕТ мы получаем 2*N/3 вариантов.
То есть спросить про деление на 3 - это вопрос хуже.
Аналогично любой другой первый вопрос хуже.
, они тоже подтверждают это.
Или есть какой-то интерес именно в доказательстве?
(Если есть, то мне кажется нужно тогда брать какие-нибудь выборки данных (чем их больше и из различных диапазонов тем лучше) и проверять какое количество вопросов получится при твоем алгоритме и сравниваемом). Математически (и чтобы было убедительно), мне кажется будет тяжело доказать.
Конструктивно (и тоже чтобы было убедительно) тоже тяжело. Например:
Цитата Сообщение от odip Посмотреть сообщение
Изначально у нас N вариантов ответа.
Первый шаг: делится ли n на 2.
При ответе ДА мы получаем N/2 вариантов.
При ответе НЕТ мы получаем N/2 вариантов.
Если же спросить что-нибудь другое, например делится ли наше число на 3.
При ответе ДА мы получаем N/3 вариантов.
При ответе НЕТ мы получаем 2*N/3 вариантов.
То есть спросить про деление на 3 - это вопрос хуже.
Аналогично любой другой первый вопрос хуже.
Но если я первый вопрос задам о делении на 3. (вроде бы и не самый оптимальный вопрос). А следующий вопрос задам о делении на 2. То как и в твоем алгоритме (на втором шаге) я на столько же уменьшил число возможных комбинаций.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru