VPF::[C++] Игра "Угадай число" - Форум программистов

WaveTheDragon

Дата 29.1.2009, 18:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.1.2009

Репутация: нет
Всего: нет

Оригинал задачи можно найти на -> этом <- сайте.
Проверить правильность задачи можно -> на том же портале <-, зарегестрировавшись.
Краткое условие задачи:
Угадай число II

Time limit = 5 секунд(ы)
(см. задача 018) Петя загадал рациональное число (несократимую дробь) больше нуля и меньше единицы, со знаменателем меньше либо равно N. Вы можете задавать ему вопросы типа

"верно ли, что число меньше r?"

где вместо r можно подставлять любое рациональное число.

По числу N определите минимальное число вопросов M(N), которых наверняка хватит, чтобы узнать загаданное Петей число. То есть такое число M, что существует алгоритм задавания вопросов, который при данном N для всех возможных вариантов загаданного числа узнает, чему равно загаданое число, меньше либо равно, чем за M вопросов, и алгоритма с меньшим M не существует.

Вход. Вход состоит из одной строчки, в которой находится натуральное число N, 1 < N < 2000000.

Выход. Одна строчка, в которой находится натуральное число — минимальное число вопросов, которого аверняка хватит, чтобы угадать загаданное число.

Вход#1
2
Выход#1
0

Вход#2
4
Выход#2
3

Вход#3
5
Выход#3
4

А теперь об вознаграждени.
Возможно 3 варианта
1) Денежный- до (ваша цена)руб На Яндекс.деньги (до 4 февраля)
2) Пивной - три пинты любого(в разумных пределах) разливного или пять бутылок бутылочного(тоже любого) пива с доставкой на дом(Москва) . smile

3) Особый - если решение этой задачи вам ничего не стоило и вы доброй души человек - можно обойтись огромным СПАСИБО и вечной дружбой и поддержкой smile

Это сообщение отредактировал(а) WaveTheDragon - 29.1.2009, 23:01

stat007

Дата 29.1.2009, 19:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 521
Регистрация: 9.10.2008

Репутация: нет
Всего: -4

Могу написать программу, угадывания числа, которое загадал компьютер с N-ом количеством попыток.

WaveTheDragon

Дата 29.1.2009, 19:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.1.2009

Репутация: нет
Всего: нет

С N-ом количеством попыток любой дурак может.
Я даже саму программу написал.
Но с алгоритмом проблемы. В Time limit = 5 секунд не укладывается

Kakadu

Дата 30.1.2009, 00:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 273
Регистрация: 19.3.2008

Репутация: 7
Всего: 7

гипотеза
сложим значения функции Эйлера (количество чисел, взаимно простых с заданным) для всех натуральных чисел от 2 до N. От суммы возьмем двоичный логарифм плюс 1. Это и будет ответ. Влезет ли это в 5 секунд - не знаю. при желании это можно сгенерировать заранее и как константу вбить. Функция Эйлера в Java должна встроенная быть - поищите.

--------------------

Добрые мариносы долго кормили украдкой маленьких зерлингов. От этой украдки зерлинги пухли и дохли

WaveTheDragon

Дата 30.1.2009, 00:18 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.1.2009

Репутация: нет
Всего: нет

Гипотеза неплохая, только вот... кол-во операций функции эйлера ~N.
N операций по эйлеру * N , где N=2000000...
Ну я не знаю, можешь попробовать=)
Если получится, с меня См. выше smile

WaveTheDragon

Дата 30.1.2009, 07:18 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.1.2009

Репутация: нет
Всего: нет

7:20
время вышло.

crin

Дата 31.1.2009, 13:40 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 15.11.2008

Репутация: нет
Всего: 1

дели интервал надва, конай в сторону бинарного поиска

Это сообщение отредактировал(а) crin - 31.1.2009, 13:41

Веталька

Дата 31.1.2009, 20:28 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 338
Регистрация: 2.11.2008

Репутация: нет
Всего: 6

Скачай себе паскаль АВС, там в примерах точно такая прога есть, ну а код перипишеш на что уже надо.

--------------------

Ради зачета студент идет на все, даже на лекции........................

WaveTheDragon

Дата 1.2.2009, 11:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.1.2009

Репутация: нет
Всего: нет

Цитата

дели интервал надва, конай в сторону бинарного поиска

Дело не в поиске количества вопросов, а в количестве дробей. их будет за 4*10^10. А таймлимит у нас насколько помнишь 5 секунд а не 20 минут.

Цитата

Скачай себе паскаль АВС, там в примерах точно такая прога есть, ну а код перипишеш на что уже надо.

Там для дроби со знаменателем, равным N.

А вообще задача уже решена.
Решение могу выложить для желающих.

airyashov

Дата 2.2.2009, 08:13 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 284
Регистрация: 1.7.2008

Репутация: 1
Всего: 6

Выложите посмотреть интересно, наверное функция от N к-нибуть.

--------------------

icq:3(один)7748666
mail:airyashov( а )inbox.ru

WaveTheDragon

Дата 2.2.2009, 16:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.1.2009

Репутация: нет
Всего: нет

Код


#include <iostream>

#include <memory.h>
using namespace std;


int phi[2000001];

int from[2000001];

int N;

int Phi(int n) // "lazy evaluations"

{
    int par = n;

    if (phi[n]!=-1) return phi[n];

    int p = from[n];

    int res = 1;

    while (from[n]==p)  // exclude prime number p from n totally

    {
        res*=p;
        n/=p;

    }
    res/=p;
    res*=(p-1);


    return (phi[par] = res*((n==1)?1:Phi(n))); // use well known formula

}

int main(void)

{
    cin >> N;

    memset(from, 0, sizeof(from));

    for (int i = 2; i <= N; i++)

    {
        if (from[i] == 0)

        {
            for (int j = i; j <= N; j+=i)

            {
                from[j] = i;

            }
        }
    }
    memset(phi, -1, sizeof(phi));

    phi[0] = phi[1] = 0;

    long long r = 0;

    for (int i = 1; i <= N; i++)

    {
        r+=Phi(i);

    }
    int res = 0;

    long long pw = 1;

    while (pw<r)

    {
        pw*=2;

        res++;
    }
    cout << res << endl;

    return 0;
}

Добавлено через 1 минуту и 7 секунд
И немного теории...
Есть такое понятие - фи-функция. Определение такое - Phi(x) = кол-во чисел на отрезке 1..x-1 которые взаимнопросты с x. Т.е. по простому - колво несократимых дробей со знаменателем x. Легко доказать что:
1) Для двух взаимнопростых чисел m и n, не равных 1, Phi(m*n)=Phi(m)*Phi(n). Например, Phi(2)=1, Phi(3)=2 --->> Phi(6)=2
2) Если p - простое число, n!=0, то Phi(p^n) = (p-1)*p^(n-1)
Из этого получается простая формула для Phi(n) по разложению n на простые множители:
n = p1^k1*p2^k2*.... --->> Phi(n) = (p1-1)*p1^(k1-1)*(p2-1)*p2^(k2-1)*...
Осталось только сгенерить простые числа до 2000000 решетом Эратосфена, и всё.

Dmi3ev

Дата 2.2.2009, 23:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 5
Всего: 41

Цитата

Есть такое понятие - фи-функция.

да ладно?

Kakadu говорил про функцию Эйлера (возможно он говорил именно про это).
Но ты его не слушал.
А это она и есть, это же фи-функция Эйлера.
smile

вот что ты говорил на эту тему

Цитата

А можно было порыться немного и найти фи-функцию Эйлера, которая в итоге закономерно стала основой решения этой задачи smile

--------------------

WaveTheDragon

Дата 3.2.2009, 00:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.1.2009

Репутация: нет
Всего: нет

Да, я слепой нуп =)
Набрав в педивикии функцию Эйлера увидел страшную формулу, напоминающую моё первое решение не влезающее во время.
Виват Kakadu.
А я пошел smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »