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

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

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

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

12.03.2014, 20:52. Просмотров 1343. Ответов 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;
    }
}
Если кто имеет идеи по решению и\или решение прошу предоставить.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2014, 20:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос "Забавная игра" (C++):

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Консольная "графика", игра "Тетрис". Фигуры перестают прорисовываться на определенном этапе - C++
Доброго времени! Написал на днях тетрис (в консоле) с использованием, кажется это называется WinApi. В цикле вызывается функция...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

9
Fene4ka_
91 / 91 / 16
Регистрация: 24.01.2014
Сообщений: 1,215
12.03.2014, 20:52 #2
ALEXKIRNAS, алгоритм - введенное число перевести в 2-ую систему -> записать в массив -> сдвинуть числа -> записать в массив -> проверить повторилось число или нет -> если нет, повторять 2 последних дейсвтия, покуда не повторится -> из элементов массива найти максимальное -> вывести в файл
0
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
12.03.2014, 20:58  [ТС] #3
задача взята с асмп.ру

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

Добавлено через 1 минуту
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться.
циклический сдвиг, однако
0
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
0
ValeryS
Модератор
6654 / 5063 / 470
Регистрация: 14.02.2011
Сообщений: 16,930
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 вывести максимальное
и все никаких массивов
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2014, 19:28
Привет! Вот еще темы с ответами:

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

Реализовать структуру "Анкета" с полями "Фамилия", "Пол" и "Адрес" - C++
Здравствуйте. Проходим тему Структуры, не могу понять, как определить количество, само задание: #include &lt;iostream&gt; #include...

по строкам.замените в слове сочетание "му" на "а" , а букву "ы" на "ца". очень нужно - C++
замените в слове сочетание &quot;му&quot; на &quot;а&quot; , а букву &quot;ы&quot; на &quot;ца&quot;. очень нужно Добавлено через 21 час 4 минуты неужели никто не знает...

Структура «Преподаватель» с полями "ФИО", "стаж", "категория", "нагрузка" - C++
Функция - расчёт зарплаты по нагрузке и оплате часа для определенной категории. Категория Оплата часа Вторая 150 Первая 200 ...


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

Или воспользуйтесь поиском по форуму:
10
Yandex
Объявления
13.03.2014, 19:28
Ответ Создать тему
Опции темы

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