Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Задача про коробки от Гугла как реализовать
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Alexiski Alexiski на форуме
Любитель давать советы
 
Сообщений: 4,274
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию Задача про коробки от Гугла как реализовать - 17.10.2008, 17:18

Есть N коробок. Все они открыты. Человек проходит и закрывает каждую вторую коробку. Затем проходит по каждой третей коробки, если она открыта закрывает, если закрыта открывает. Потом по каждой четвёртой и так до N. Сколько коробок останутся открытыми после всех этих действий?
Ответить с цитированием
  (#2 (permalink)) Старый
Alexiski Alexiski на форуме
Любитель давать советы
 
Сообщений: 4,274
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию Задача про коробки от Гугла как реализовать - 17.10.2008, 17:18

Есть N коробок. Все они открыты. Человек проходит и закрывает каждую вторую коробку. Затем проходит по каждой третей коробки, если она открыта закрывает, если закрыта открывает. Потом по каждой четвёртой и так до N. Сколько коробок останутся открытыми после всех этих действий?
Ответить с цитированием
  (#3 (permalink)) Старый
Jonano Jonano вне форума
Специалист
 
Аватар для Jonano
 
Сообщений: 3,541
Сказал(а) спасибо: 2
Поблагодарили 14 раз(а) в 14 сообщениях
Регистрация: 19.04.2005
По умолчанию 17.10.2008, 17:49

А надо им сходу ответить или можно программу написать?
Ответить с цитированием
  (#4 (permalink)) Старый
Jonano Jonano вне форума
Специалист
 
Аватар для Jonano
 
Сообщений: 3,541
Сказал(а) спасибо: 2
Поблагодарили 14 раз(а) в 14 сообщениях
Регистрация: 19.04.2005
По умолчанию 17.10.2008, 17:49

А надо им сходу ответить или можно программу написать?
Ответить с цитированием
  (#5 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 17.10.2008, 18:40

Опытным путем установлено, что количество открытых коробок равно минимальному количеству последовательных нечетных чисел, сумма которых больше N.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 17.10.2008, 18:40

Опытным путем установлено, что количество открытых коробок равно минимальному количеству последовательных нечетных чисел, сумма которых больше N.
Ответить с цитированием
  (#7 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 17.10.2008, 19:14

Красивая задача. В смысле, ответ красивый.

Судя по моим первым прикидкам (без компьютера), останутся открытыми столько коробок, сколько существует полных квадратов, не превосходящих N (т.е., сколько из чисел 1, 4, 9, 16, ... не превосходит N).

Например, если N = 10, то останутся 3 открытые коробки (с номерами 1, 4, 9, если их нумеровать с 1);
если N = 23, то останутся открытыми коробки с номерами 1, 4, 9, 16 - всего 4 штуки. И т.д.


В общем, чтобы ответить на вопрос "Сколько?", нужно просто извлечь из N квадратный корень и ответ округлить в меньшую сторону.
Ответить с цитированием
  (#8 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 17.10.2008, 19:14

Красивая задача. В смысле, ответ красивый.

Судя по моим первым прикидкам (без компьютера), останутся открытыми столько коробок, сколько существует полных квадратов, не превосходящих N (т.е., сколько из чисел 1, 4, 9, 16, ... не превосходит N).

Например, если N = 10, то останутся 3 открытые коробки (с номерами 1, 4, 9, если их нумеровать с 1);
если N = 23, то останутся открытыми коробки с номерами 1, 4, 9, 16 - всего 4 штуки. И т.д.


В общем, чтобы ответить на вопрос "Сколько?", нужно просто извлечь из N квадратный корень и ответ округлить в меньшую сторону.
Ответить с цитированием
  (#9 (permalink)) Старый
Jonano Jonano вне форума
Специалист
 
Аватар для Jonano
 
Сообщений: 3,541
Сказал(а) спасибо: 2
Поблагодарили 14 раз(а) в 14 сообщениях
Регистрация: 19.04.2005
По умолчанию 17.10.2008, 22:10

Alison, твоё предположение верно. Сделал тест, прогнал при N от 2 до 100000, везде результат равен округлённому квадратному корню.
Вот код:
Код:
#include "stdio.h"
#include "memory.h"
#include "math.h"
#include "conio.h"

int ExecuteTest(int iCont);

int main(int argc, char* argv[])
{
    /*int lCount;
    printf("N = ");
    scanf("%d", &lCount);

    int lRes = ExecuteTest(lCount);

    printf("Result = %d\n", lRes);
    printf("SQRT(N) = %f\n", sqrt((double)lCount));*/

    for(int i = 2;i<100000;i++)
    {
        int lRes = ExecuteTest(i);
        int q = (int)sqrt((double)i);

        if(lRes != q)
        {
            printf("N = %d\n", i);
        }
    }

    printf("Test ended");

    getch();

    return 0;
}

int ExecuteTest(int iCount)
{
    int lRet = 0;

    char *lMass = new char[iCount];
    if(lMass != NULL)
    {
        memset(lMass, 1, iCount);
    
        for(int i=2; i<=iCount;i++)
        {
            int lIndex = i - 1;
            while(lIndex < iCount)
            {
                lMass[lIndex] = 1 - lMass[lIndex];
                lIndex += i;
            }
        }
        
        for(int i=0; i<iCount; i++)
        {
            lRet += lMass[i];
        }

        delete lMass;
    }

    return lRet;
}
Ответить с цитированием
  (#10 (permalink)) Старый
Jonano Jonano вне форума
Специалист
 
Аватар для Jonano
 
Сообщений: 3,541
Сказал(а) спасибо: 2
Поблагодарили 14 раз(а) в 14 сообщениях
Регистрация: 19.04.2005
По умолчанию 17.10.2008, 22:10

Alison, твоё предположение верно. Сделал тест, прогнал при N от 2 до 100000, везде результат равен округлённому квадратному корню.
Вот код:
Код:
#include "stdio.h"
#include "memory.h"
#include "math.h"
#include "conio.h"

int ExecuteTest(int iCont);

int main(int argc, char* argv[])
{
    /*int lCount;
    printf("N = ");
    scanf("%d", &lCount);

    int lRes = ExecuteTest(lCount);

    printf("Result = %d\n", lRes);
    printf("SQRT(N) = %f\n", sqrt((double)lCount));*/

    for(int i = 2;i<100000;i++)
    {
        int lRes = ExecuteTest(i);
        int q = (int)sqrt((double)i);

        if(lRes != q)
        {
            printf("N = %d\n", i);
        }
    }

    printf("Test ended");

    getch();

    return 0;
}

int ExecuteTest(int iCount)
{
    int lRet = 0;

    char *lMass = new char[iCount];
    if(lMass != NULL)
    {
        memset(lMass, 1, iCount);
    
        for(int i=2; i<=iCount;i++)
        {
            int lIndex = i - 1;
            while(lIndex < iCount)
            {
                lMass[lIndex] = 1 - lMass[lIndex];
                lIndex += i;
            }
        }
        
        for(int i=0; i<iCount; i++)
        {
            lRet += lMass[i];
        }

        delete lMass;
    }

    return lRet;
}
Ответить с цитированием
  (#11 (permalink)) Старый
Alexiski Alexiski на форуме
Любитель давать советы
 
Сообщений: 4,274
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 18.10.2008, 00:44

Ну, что результат для данного числа зависит от четности количества различных делителей, я допер довольно быстро.
А вот что эта самая четность зависит только от того, является ли число полным квадратом, я сначала вообще не допер.
Когда факт был уже известен, прикинул доказательство через разложение на простые множители - таки да.

А оказалось все совсем просто:
Каждый несобственный делитель всегда появляется в паре с другим: N = a * b
И только у полных квадратов один из делителей появляется без пары: N = a * a
Ответить с цитированием
  (#12 (permalink)) Старый
Alexiski Alexiski на форуме
Любитель давать советы
 
Сообщений: 4,274
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 18.10.2008, 00:44

Ну, что результат для данного числа зависит от четности количества различных делителей, я допер довольно быстро.
А вот что эта самая четность зависит только от того, является ли число полным квадратом, я сначала вообще не допер.
Когда факт был уже известен, прикинул доказательство через разложение на простые множители - таки да.

А оказалось все совсем просто:
Каждый несобственный делитель всегда появляется в паре с другим: N = a * b
И только у полных квадратов один из делителей появляется без пары: N = a * a
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 18.10.2008, 06:32

Графически хорошо видно - четкие полоски ровно по квадратам (или по сумме нечетных, что то же самое, но дошло не сразу).
Ответить с цитированием
  (#14 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 18.10.2008, 06:32

Графически хорошо видно - четкие полоски ровно по квадратам (или по сумме нечетных, что то же самое, но дошло не сразу).
Ответить с цитированием
  (#15 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 18.10.2008, 20:29

Alexiski, мне кажется, что это можно показать попроще.

N (>1) является полным квадратом <=> в его разложении на простые множители все степени являются четными (это очевидно) <=> общее количество различных делителей N нечетно <=> N имеет четное количество делителей, отличных от 1.

Остается применить индукцию по N. Для маленьких значений N можно проверить в лоб. Предположим, что для N-1 все верно. Проверим для N. Последний, N-й проход на состояния (открытая-закрытая) предыдущих коробок не влияет, поэтому для них все верно (если номер - полный квадрат, то она открытая, а если нет, то закрытая).
Если N - полный квадрат, то количество делителей, больших 1, четно, изначально коробка открытая, поэтому операций закрыть-открыть будет проделано четное число, так что коробка в результате будет открытой.
Если N не является полным квадратом, то, наоборот, закрытой (т.к. в этом случае число делителей, отличных от 1, нечетно).
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите, задача по прологу, срочно...задача с высказываниями 4ixOn Prolog 6 10.07.2011 23:29
Помогите, задача по прологу, срочно...задача о станках 4ixOn Prolog 3 09.07.2011 22:48
Формально-логическая задача как ее реализовать Амелия Lisp 0 19.05.2011 21:46
Задача по MPI 45$ Naikon1988 Задания за деньги 2 22.12.2010 18:12
Не могу зайти на сайты Гугла. Katrina_ Любые вопросы от новичков 24 11.12.2010 22:46
Как откоючить пользовательский поиск Гугла? chocogel Любые вопросы от новичков 1 21.12.2008 12:49
OpenGL как сделать стенки коробки прозрачными imported_Nikss Delphi 3 18.09.2007 17:52
Приколы гугла gromozeka Юмор 6 30.05.2006 12:28
Задача про козу, капусту и волка как реализовать MP Lisp 3 25.05.2006 01:04
задача на Си int33 Задания за деньги 1 14.04.2006 17:53
Задача: Последовательность как реализовать oleg88kpuk Алгоритмы 0 09.03.2005 21:10
А,В,С- задача про них!! Anonymous Вопросы начинающих программистов 0 08.01.2004 22:22



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов