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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
#1

Минимальное число шагов - C++

28.03.2010, 22:19. Просмотров 1181. Ответов 17
Метки нет (Все метки)

Задание такое:
Дано целое неотрицательное число N (0<=N<=1000000). С ним можно делать следующее:
- увеличить на 1
- уменьшить на 1
- поделить на 2 если чётное
Требуется получить 0 за минимальное число шагов.

А вопрос вот в чём: зачем нужно увеличивать на 1??? Если всегде целесообразнее уменьшать на 1 и делить на 2 если чётное? Не могли бы вы привести пример числа, которое нужно было бы увеличить на 1?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.03.2010, 22:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Минимальное число шагов (C++):

Посчитать среднее число шагов в двоичном поиске для массива - C++
Всем доброго времени суток,помогиет пожалуйста написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32...

Требуется составить программу, вычисляющую для заданного n последовательность Хейеса, подсчитывающую число шагов в ней и находящую ее вершину - C++
2. Последовательность Хейеса Рассмотрим некоторое натуральное число n. Если оно четное, то разделим его на 2, иначе -- ум-ножим на 3 и...

Получить из пары чисел пару равных чисел за как можно меньшее число шагов с помощью двух заданных операций - C++
Господа, нужна ваша помощь. Собственно пересказ задачи: Результатом применения операции 1 к паре натуральных чисел (a, b) является пара...

Минимальное число - C++
Есть задача, ее условие Требуется написать программу, которая из цифр двух натуральных чисел создает наименьшее возможное число,...

Минимальное число в матрице - C++
Здравствуйте помогите пожалуйста написать программу для поиска минимального числа в матрице (двумя способами) просто вобше не шарю в...

Минимальное число в последовательности - C++
Написать программу, которая определяет минимальное число во введенной с клавиатуры последовательности чисел (длина последовательности не...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Зоти Сергей
228 / 226 / 13
Регистрация: 18.12.2009
Сообщений: 316
28.03.2010, 22:40 #2
Да нет такого числа, вроде.
Всегда, если число нечетное отнимаете от него 1, как и сами написали.
Иначе же делите на 2.
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
28.03.2010, 22:49  [ТС] #3
Вот и я так думаю что нет... А мне сказали что есть.... Но я никак не могу придумать такое число....
easybudda
Модератор
Эксперт CЭксперт С++
9530 / 5523 / 932
Регистрация: 25.07.2009
Сообщений: 10,608
28.03.2010, 23:12 #4
WiDe, задача по определению решения не имеет:

Цитата Сообщение от WiDe Посмотреть сообщение
- увеличить на 1
- уменьшить на 1
- поделить на 2 если чётное
Требуется получить 0 за минимальное число шагов.
Единственное нечётное число, которое таки прийдётся увеличивать на 1 - это единица, т.к. нечётные числа нельзя делить по условию. То есть получится бесконечный цикл.

Добавлено через 1 минуту
Хотя нет. От единицы можно просто один отнять... Ну тогда не знаю... Наверное, чтобы было.
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 482
29.03.2010, 00:05 #5
Требуется получить 0 за минимальное число шагов.

возьмём число 15

1 способ (только вычитаем)

15-1=14
14/2=7
7-1=6
6/2=3
3-1=2
2/2=1
1-1=0

7 действий

2 способ (сложение + вычитание)
15+1=16
16/2=8
8/2=4
4/2=2
2/2=1
1-1=0

6 действий

Собственно вот и ответ
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
29.03.2010, 00:27  [ТС] #6
т.е. получается если число изначально нечётное, то лучше +1? Я так думаю...

Добавлено через 1 минуту
Блин, хотя нет... с 25 так не прокатывает уже...
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 482
29.03.2010, 01:05 #7
В общем тут получается что если число на 1 меньше любой степени двойки т.е. 8 16 32 64 то надо прибавлять.

Щас всё посчитаем) 10 мин.

Добавлено через 14 минут
число 7

-
7-1=6
6/2=3
3-1=2
2/2=1
1-1=0
5 действий

+ и -

7+1=8
8/2=4
4/2=2
2/2=1
1-1=0
5 действий

для 15 считали уже 7 и 6

для 31 будет 9 и 7

для 63 будет 11 и 8

для 127 будет 13 и 9

Отсюда видно что если будет например число 125
125-1=124
124/2=62
62/2=31

+9 ходов от 31 = 12

получится 125 +1 + 1 + 1 и ещё 9 ходов от 128 =12, то тут без разницы

если возьмём 126 то будет 12 ходов с минусом и 11 где плюс и минус.

По идее получается что если число меньше 2^n на n-5 то его целесобразно подгонять к 2^n
Ну это предположение надо проверить для больших чисел!

Добавлено через 6 минут
Нет я ошибаюсь... алгоритм тут очень уж суровый походу...
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
29.03.2010, 19:36  [ТС] #8
Хм, ща поем и проверю твою теорию=)

Добавлено через 55 минут
Ну а если просто сделать три условия: если число равно 2 в какойто степени -1 то к числу прибавить 1; если оно чётное, то поделить его на два; в остальных случаях вычесть единицу? Только вот как узнать равно ли число двойке в какой-либо степени минус один?

Добавлено через 4 часа 41 минуту
Ну что, есть у кого ещё какие идеи?
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 482
29.03.2010, 23:00 #9
WiDe, Узнать то легко, напрмиер
C++
1
2
3
4
n=255;
for (i=4;pow(2,i)<1000000;i++)
if (pow(2,i)-1==n)
//то прибавляем +1
И кстати такую проверку желательно делать на каждом шаге, т.к. например для числа 510 быстрее будет:
510/2=255
255+1=256

Короче примерно так... Ты С++ давно изучаешь? Просто интересно задача правда мутная), или она просто решается... Самому даже интересно.

Хотя есть мысля что тут можно придумать вычислительную схему с возвратом, но я её тока прохожу
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
29.03.2010, 23:58  [ТС] #10
С++ изучаю только около полугода...

Цитата Сообщение от From_Tula Посмотреть сообщение
Просто интересно задача правда мутная), или она просто решается...
Это мне тоже интересно=)) Просто задание такое на конкурсе дали=)
neske
1482 / 849 / 76
Регистрация: 26.03.2010
Сообщений: 2,917
30.03.2010, 00:23 #11
Я думаю в первую очередь число нужно довести до вида - двойки в n степени, за минимальное число шагов разумеется
Сильно не ругаться :P

Добавлено через 13 минут
Именно поэтому, как видно из поста From_Tula, в вариантах с числами 31, 63, 127, 255, с "+" шагов меньше.
Somebody
2788 / 1602 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
30.03.2010, 00:50 #12
Поиск в ширину по графу с вершинами-числами и рёбрами-преобразованиями

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
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
 
using namespace std;
 
const int maxN = 1000000;
struct vertex {int dist; int prev; bool used;};
 
void go(vector< vertex >& v, int from, int to, queue< int >& q)
{
    if (v[to].used)
        return;
    v[to].dist = v[from].dist + 1;
    v[to].prev = from;
    v[to].used = true;
    q.push(to);
}
 
int main()
{
    int n;
    vector< vertex > v(maxN + 1);
    queue< int > q;
    cin >> n;
    v[0].dist = 0;
    v[0].used = 1;
    q.push(0);
    while (!q.empty())
    {
        int c = q.front();
        q.pop();
        if (c <= maxN) go(v, c, c + 1, q);
        if (c > 0) go(v, c, c - 1, q);
        if (c <= maxN / 2) go(v, c, c * 2, q);
    }
    for (int c = n; c != 0; c = v[c].prev)
        cout << c << endl;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
30.03.2010, 09:05  [ТС] #13
Значит делаю так:
сперва проверяю на чётность
потом проверяю на 2^n-1
и в остальных случаях просто вычитаю 1

Кстати, мне препод говорил, что существует специальная функция определения чётности числа. Это какая?

Добавлено через 2 минуты
Цитата Сообщение от neske Посмотреть сообщение
Я думаю в первую очередь число нужно довести до вида - двойки в n степени, за минимальное число шагов разумеется
хз, можно попробовать=)

Somebody, спасибо! Приеду из универа, погляжу...

Добавлено через 22 минуты
Somebody, пока просто закинул данный код в Visual C++, он откомпилировался, но не работает. Ввожу число, немного тормозит а потом ошибка вылетает.
neske
1482 / 849 / 76
Регистрация: 26.03.2010
Сообщений: 2,917
30.03.2010, 10:11 #14
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
int main ()
{
    int pow(int,int);
    int ch=0; // число, вводимое пользователем.
    int counter=0; // счетчик шагов.
    int n;
    cout << "Vvedite chislo- " << endl;
    cin >> ch;
 
 
    while( ch>0 )
    {
        if ( (ch%2==0) )
        {
            counter+=1;
            cout << "Shag " << counter << ": " 
                 << ch << " /2= " << ch=ch/2 << endl;
 
        }
        else 
        {
            for (n=4; pow(2,n)<100000; n++) // проверка.
                if ( pow(2,n)-1==ch )
                {
                    counter+=1;
                    cout << "Shag " << counter << ": " 
                         << ch << " +1= " << ch+1 << endl;
                }
                else
                {
                    counter+=1;
                    cout << "Shag " << counter << ": " 
                         << ch << " -1= " << ch-1 << endl;
                }
        }
    }
cout << "Itogo " << counter << " shagov." << endl;
 
    return 0;
}
Прошу посмотреть мое решение, но выдает ошибку.. ищу.

Кстати, еще тут одна штука. Проверку, на что что число может-быть в виде 2n-1, нужно делать не только в начале, но и при каждом шаге, где число нечетно.
Somebody
2788 / 1602 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
30.03.2010, 19:45 #15
Цитата Сообщение от WiDe Посмотреть сообщение
Somebody, пока просто закинул данный код в Visual C++, он откомпилировался, но не работает. Ввожу число, немного тормозит а потом ошибка вылетает.
В 34-й строке надо < вместо <=.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.03.2010, 19:45
Привет! Вот еще темы с ответами:

Найти минимальное число - C++
Вообщем есть 10 переменных.нужно найти какое из них наименьшее.С if слишком громоздко выходит

Минимальное число белых слонов - C++
Имеется шахматная доска N × M клеток. Некоторые поля на ней заняты белыми фигурами, но не слонами (конь, ладья, король, ферзь) и белыми...

Минимальное положительное целое число - C++
Братья,нужна помощь. Вычислить минимальное положительное целое число, которое не является точно представимым в типе double. Как найти...

Найти минимальное положительное число - C++
все вычисляет верно, но желательно оптимизировать, может знает кто? #include &lt;iostream&gt; #include &lt;math.h&gt; using namespace std; ...


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

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

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