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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
28.03.2010, 22:19     Минимальное число шагов #1
Задание такое:
Дано целое неотрицательное число 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++ Найти минимальное число
Минимальное число в матрице 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
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
28.03.2010, 23:12     Минимальное число шагов #4
WiDe, задача по определению решения не имеет:

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

Добавлено через 1 минуту
Хотя нет. От единицы можно просто один отнять... Ну тогда не знаю... Наверное, чтобы было.
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 469
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
Сообщений: 469
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
Сообщений: 469
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
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
30.03.2010, 00:23     Минимальное число шагов #11
Я думаю в первую очередь число нужно довести до вида - двойки в n степени, за минимальное число шагов разумеется
Сильно не ругаться :P

Добавлено через 13 минут
Именно поэтому, как видно из поста From_Tula, в вариантах с числами 31, 63, 127, 255, с "+" шагов меньше.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 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
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
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
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
30.03.2010, 19:45     Минимальное число шагов #15
Цитата Сообщение от WiDe Посмотреть сообщение
Somebody, пока просто закинул данный код в Visual C++, он откомпилировался, но не работает. Ввожу число, немного тормозит а потом ошибка вылетает.
В 34-й строке надо < вместо <=.
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
30.03.2010, 23:51  [ТС]     Минимальное число шагов #16
Цитата Сообщение от Somebody Посмотреть сообщение
В 34-й строке надо < вместо <=.
Теперь работает, но программа число 1000000 обрабатывает более 2 сек. А мне по заданию надо макс 2 сек.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
31.03.2010, 21:54     Минимальное число шагов #17
Цитата Сообщение от WiDe Посмотреть сообщение
Теперь работает, но программа число 1000000 обрабатывает более 2 сек. А мне по заданию надо макс 2 сек.
А ты случаем не в Debug конфигурации компилил, когда время мерял? У меня сейчас скомпиленная в G++ (DevC++) на 5000000 уложилась в 2 секунды на процессоре 800 МГц.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.03.2010, 23:50     Минимальное число шагов
Еще ссылки по теме:

Требуется составить программу, вычисляющую для заданного n последовательность Хейеса, подсчитывающую число шагов в ней и находящую ее вершину C++
Вычислить за минимальное число операций C++
Посчитать среднее число шагов в двоичном поиске для массива C++

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

Или воспользуйтесь поиском по форуму:
WiDe
10 / 10 / 1
Регистрация: 23.02.2010
Сообщений: 120
31.03.2010, 23:50  [ТС]     Минимальное число шагов #18
Ну понятно тогда, я в Debug делал...
Yandex
Объявления
31.03.2010, 23:50     Минимальное число шагов
Ответ Создать тему
Опции темы

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