Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
WiDe
10 / 10 / 2
Регистрация: 23.02.2010
Сообщений: 120
#1

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

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

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

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

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

Удалять последнюю цифру числа, пока число не станет меньше 10, посчитать количество шагов
Надо создать програму которая стрирает последнюю цифру числа пока число не...

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

Получить из пары чисел пару равных чисел за как можно меньшее число шагов с помощью двух заданных операций
Господа, нужна ваша помощь. Собственно пересказ задачи: Результатом...

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

17
Зоти Сергей
229 / 227 / 65
Регистрация: 18.12.2009
Сообщений: 316
28.03.2010, 22:40 #2
Да нет такого числа, вроде.
Всегда, если число нечетное отнимаете от него 1, как и сами написали.
Иначе же делите на 2.
0
WiDe
10 / 10 / 2
Регистрация: 23.02.2010
Сообщений: 120
28.03.2010, 22:49  [ТС] #3
Вот и я так думаю что нет... А мне сказали что есть.... Но я никак не могу придумать такое число....
0
easybudda
Модератор
Эксперт CЭксперт С++
10051 / 5971 / 1491
Регистрация: 25.07.2009
Сообщений: 11,306
28.03.2010, 23:12 #4
WiDe, задача по определению решения не имеет:

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

Добавлено через 1 минуту
Хотя нет. От единицы можно просто один отнять... Ну тогда не знаю... Наверное, чтобы было.
0
From_Tula
40 / 40 / 10
Регистрация: 22.05.2009
Сообщений: 486
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 действий

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

Добавлено через 1 минуту
Блин, хотя нет... с 25 так не прокатывает уже...
0
From_Tula
40 / 40 / 10
Регистрация: 22.05.2009
Сообщений: 486
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 минут
Нет я ошибаюсь... алгоритм тут очень уж суровый походу...
1
WiDe
10 / 10 / 2
Регистрация: 23.02.2010
Сообщений: 120
29.03.2010, 19:36  [ТС] #8
Хм, ща поем и проверю твою теорию=)

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

Добавлено через 4 часа 41 минуту
Ну что, есть у кого ещё какие идеи?
0
From_Tula
40 / 40 / 10
Регистрация: 22.05.2009
Сообщений: 486
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

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

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

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

Добавлено через 13 минут
Именно поэтому, как видно из поста From_Tula, в вариантах с числами 31, 63, 127, 255, с "+" шагов меньше.
1
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
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');
}
1
WiDe
10 / 10 / 2
Регистрация: 23.02.2010
Сообщений: 120
30.03.2010, 09:05  [ТС] #13
Значит делаю так:
сперва проверяю на чётность
потом проверяю на 2^n-1
и в остальных случаях просто вычитаю 1

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

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

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

Добавлено через 22 минуты
Somebody, пока просто закинул данный код в Visual C++, он откомпилировался, но не работает. Ввожу число, немного тормозит а потом ошибка вылетает.
0
neske
1527 / 894 / 192
Регистрация: 26.03.2010
Сообщений: 3,074
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, нужно делать не только в начале, но и при каждом шаге, где число нечетно.
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
30.03.2010, 19:45 #15
Цитата Сообщение от WiDe Посмотреть сообщение
Somebody, пока просто закинул данный код в Visual C++, он откомпилировался, но не работает. Ввожу число, немного тормозит а потом ошибка вылетает.
В 34-й строке надо < вместо <=.
0
WiDe
10 / 10 / 2
Регистрация: 23.02.2010
Сообщений: 120
30.03.2010, 23:51  [ТС] #16
Цитата Сообщение от Somebody Посмотреть сообщение
В 34-й строке надо < вместо <=.
Теперь работает, но программа число 1000000 обрабатывает более 2 сек. А мне по заданию надо макс 2 сек.
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
31.03.2010, 21:54 #17
Цитата Сообщение от WiDe Посмотреть сообщение
Теперь работает, но программа число 1000000 обрабатывает более 2 сек. А мне по заданию надо макс 2 сек.
А ты случаем не в Debug конфигурации компилил, когда время мерял? У меня сейчас скомпиленная в G++ (DevC++) на 5000000 уложилась в 2 секунды на процессоре 800 МГц.
0
WiDe
10 / 10 / 2
Регистрация: 23.02.2010
Сообщений: 120
31.03.2010, 23:50  [ТС] #18
Ну понятно тогда, я в Debug делал...
0
31.03.2010, 23:50
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.03.2010, 23:50

Минимальное число в матрице
Здравствуйте помогите пожалуйста написать программу для поиска минимального...

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

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


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

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