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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
#1

"Забавная игра" - C++

12.03.2014, 20:52. Просмотров 1164. Ответов 9
Метки нет (Все метки)

Есть задача:

Забавная игра
(Время: 1 сек. Память: 16 Мб Сложность: 30%)
Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 1910 = 1*24+0*23+0*22+1*21+1*20 в двоичной системе запишется как 100112.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:
10011
11001
11100
01110
00111
10011

и результатом игры, следовательно, окажется число 1*24+1*23+1*22+0*21+0*20 = 28.

Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.

Входные данные

Входной файл INPUT.TXT содержит одно целое число N (0 <= N <= 32767).

Выходные данные

Ваша программа должна вывести в выходной файл OUTPUT.TXT одно целое число, равное результату игры.

intput 19
output 28

intput 1212
output 1938

мое решение (не проходит тест 8):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
 
using namespace std;
 
int main ()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n, m=0, i, z, l, p, m1, rez;
    cin >> n;
    bool a[32]={0}, b[16]={0};
    m1=n;
    while(n){
        m++;
        n/=2;
    }
 
    n=m1;
    m1=m-1;
    while(n){
        a[m1--]=n%2;
        n/=2;
    }
 
    if(m==0) cout << 0;
    else{
        for(i=0; i<m; i++) a[i+m]=a[i];
 
        l=0; z=0; p=0;
        
        for(i=0; i<m*2; i++) 
            if(a[i]) l++;
            else {
                if(l>z) { z=l; p=i-l; }
                l=0;
            }
            if(l>z) { z=l; p=i-l; }
            
            m1=m-1;
            for(i=0; i<m; i++) b[m1--]=a[p++];
        
        n=1;
        rez=0;
        for(i=0; i<m; i++, n*=2) { 
            rez+=b[i]*n;
        }
        cout << rez;
    }
}
Если кто имеет идеи по решению и\или решение прошу предоставить.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2014, 20:52     "Забавная игра"
Посмотрите здесь:

C++ "Змейка": при нажатии клавиши игра просто останавливается
C++ Консольная "графика", игра "Тетрис". Фигуры перестают прорисовываться на определенном этапе
C++ Карточная игра "Дурак" - Ошибка загрузки dll карт
Небольшой пример. Игра "змейка" - как в ней делают препятствия C++
C++ Игра "Крестики нолики", почему не работает проверка окончания?
Игра "Чёт-Нечет" на поле NxN, перевести с Делфи на С++ C++
C++ Игра "Однорукий бандит". Кольцевая очередь. Двусвязный список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Fene4ka_
87 / 87 / 16
Регистрация: 24.01.2014
Сообщений: 1,196
12.03.2014, 20:52     "Забавная игра" #2
ALEXKIRNAS, алгоритм - введенное число перевести в 2-ую систему -> записать в массив -> сдвинуть числа -> записать в массив -> проверить повторилось число или нет -> если нет, повторять 2 последних дейсвтия, покуда не повторится -> из элементов массива найти максимальное -> вывести в файл
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
12.03.2014, 20:58  [ТС]     "Забавная игра" #3
задача взята с асмп.ру

Добавлено через 5 минут
У меня реализирован другой алгоритм:
Берем число (например 29), переводим в двоичну систему (11101), далее записую в массив и дублирую.
Получаю такой массив (1110111101). Далее ищу найбольшое скопление единиц и откуда беру число длиной ровной длине числа в двоичной системе (тут 5) (1110111101). Переводю в нормальный вид.
Fene4ka_
87 / 87 / 16
Регистрация: 24.01.2014
Сообщений: 1,196
12.03.2014, 21:06     "Забавная игра" #4
ALEXKIRNAS, интересное решение, но разве условием не является именно сдвигать числа ?
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
12.03.2014, 21:16  [ТС]     "Забавная игра" #5
да в условии так, но от нас требуется только ответ. Я уже несколько часов придумаю тесты, но моя программа ни один не завалила, а на асмп.ру она не проходит 8 тест. :-(
Fene4ka_
87 / 87 / 16
Регистрация: 24.01.2014
Сообщений: 1,196
12.03.2014, 22:26     "Забавная игра" #6
ALEXKIRNAS, a 4to za 8 test ?
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
13.03.2014, 15:49  [ТС]     "Забавная игра" #7
Если б знал, то не писал бы в форуме.
ValeryS
Модератор
6453 / 4919 / 451
Регистрация: 14.02.2011
Сообщений: 16,320
13.03.2014, 16:03     "Забавная игра" #8
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Например, десятичное число 1910 = 1*24+0*23+0*22+1*21+1*20 в двоичной системе запишется как 100112.)
я один ничего не понял
1910 в двоичной будет 11101110110
100112. откуда в двоичной системе двойка?

Добавлено через 1 минуту
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться.
циклический сдвиг, однако
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
13.03.2014, 17:38  [ТС]     "Забавная игра" #9
Здесь условие немного подпорчено. Насамом деле так:
1910 = 1*24+0*23+0*22+1*21+1*20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2014, 19:28     "Забавная игра"
Еще ссылки по теме:

C++ Реализовать функцию стрельбы для танка (игра "Танчики")
C++ Игра "Крестики-нолики": правильно выстроить поле
C++ Решить задачу на файловый ввод/вывод (игра "Города")
Найти и исправить ошибки (игра "Морской бой") C++
C++ Карточная игра "Дурак", вывод карт на экран

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6453 / 4919 / 451
Регистрация: 14.02.2011
Сообщений: 16,320
13.03.2014, 19:28     "Забавная игра" #10
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
1910

универсальная функция циклического массива сдвига переменной любой(в пределах разумного) разрядности
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned int rcl( unsigned int n // число которое нужно сдвигать
                      int r,  // разрядность числа
                      int d  // на сколько сдвинуть 
 ) 
{
int k=sizeof(int)*8; // размер int в битах
unsigned int m=(unsigned int) -1; // 0xFFFFFFFF
m>>=r-k;// создаем маску
 
n=((n>>d)||(n<<r-d))&m; // сам циклический сдвиг
return n;
 
}

т.е нужно
1 высчитать разрядность числа циклом while
2 в цикле for пройти все сдвиги с запоминанием максимального
3 вывести максимальное
и все никаких массивов
Yandex
Объявления
13.03.2014, 19:28     "Забавная игра"
Ответ Создать тему
Опции темы

Текущее время: 12:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru