Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
nicolaus2
19 / 19 / 3
Регистрация: 11.07.2010
Сообщений: 63
1

Разбивка числа

05.04.2011, 21:45. Просмотров 1278. Ответов 16
Метки нет (Все метки)

Доброго времени суток, форумчане!

Есть небольшая задачка для разминки мозгов.

Допустим, есть цепочка длины N. Сколько минимум колец нужно расцепить, чтобы из кусков можно было получить любую цепочку длины от 1 до N. Расцеплением считать не разрыв цепочки, а деление ее путем отделение одного кольца.

Например, для цепочки 21 нужно минимум 2 таких расцепление. Мы получим цепочки длинной 1, 1, 3, 5, 11 и можем сложить цепочку длинной от 1 до N.

Есть хотя бы идеи каков алгоритм решения этой задачи?

P.S.
Еще примеры, первое - длина цепочки, второе - минимальное количество расцеплений.
7 - 1
8 - 2
21 - 2
24 - 3
159 - 4
160 - 5
384 -6
2047 - 7
10239 - 9
49152 - 15
...
1 000 000 000 - 25
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2011, 21:45
Ответы с готовыми решениями:

Разбивка числа
Имеется число x типа float float x = 291.1921; Как разбить это число на два? Целая часть и...

Разбивка числа и возведение в квадрат
Здравствуйте, такая задача - дано число к примеру 9119, его нужно разбить на числа 9 , 1, 1, 9 и...

Разбивка числа на составляющие (1234 --> 1 2 3 4)
Здравствуйте. Проблема следующая: Задано натуральное число, диапазон значений слово. Определить...

Разбивка введенного числа поэлементно на массив
Мне нужно разбить введенное число с клавиатуры на массив поэлементно. В цикле должно поэлементно...

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

16
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
05.04.2011, 21:49 2
Дурь какая-то.
Как из цепочек с длинами 1, 1, 3, 5, 8 получить цепочку длиной 21?
0
nicolaus2
19 / 19 / 3
Регистрация: 11.07.2010
Сообщений: 63
05.04.2011, 22:36  [ТС] 3
Цитата Сообщение от Хохол Посмотреть сообщение
Дурь какая-то.
Как из цепочек с длинами 1, 1, 3, 5, 8 получить цепочку длиной 21?
Точно) Исправил.

Добавлено через 41 минуту
Для 21 разбивка такова. 3-1-5-1-11.

Думал сначала в сторону чисел Фибоначчи - не то.
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
05.04.2011, 22:41 4
Какого фига для 7 ответ 1?
0
05.04.2011, 22:41
nicolaus2
19 / 19 / 3
Регистрация: 11.07.2010
Сообщений: 63
05.04.2011, 22:45  [ТС] 5
Цитата Сообщение от Хохол Посмотреть сообщение
Какого фига для 7 ответ 1?
2 - 1 - 4.
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
05.04.2011, 22:46 6
Ок, какой ответ для N = 2?
0
nicolaus2
19 / 19 / 3
Регистрация: 11.07.2010
Сообщений: 63
05.04.2011, 22:48  [ТС] 7
1, по другому никак)
0
Mr.X
Эксперт С++
3188 / 1715 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
06.04.2011, 02:28 8
У автора неправильно считает 49152 – 15.
Моя программа дает 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/////////////////////////////////////////////////////////////////////////////////////////
//Допустим, есть цепочка длины N. Сколько минимум колец нужно расцепить, чтобы из кусков 
//можно было получить любую цепочку длины от 1 до N. Расцеплением считать не разрыв цепочки, 
//а деление ее путем отделение одного кольца.
//
//Например, для цепочки 21 нужно минимум 2 таких расцепление. Мы получим цепочки 
//длинной 1, 1, 3, 5, 11 и можем сложить цепочку длинной от 1 до N.
//
//Есть хотя бы идеи каков алгоритм решения этой задачи?
//
//P.S.
//Еще примеры, первое - длина цепочки, второе - минимальное количество расцеплений.
//7 - 1
//8 - 2
//21 - 2
//24 - 3
//159 - 4
//160 - 5
//384 -6
//2047 - 7
//10239 - 9
//49152 - 15
//...
//1 000 000 000 - 25 
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
int  get_unlinks_min(int  n)
{
    int  counter  = 0;
    int  L        = 0;
    int  R        = 0;
    if(n > 1)
    {
        do
        {
            ++counter;
            L =   n / 2 * 2 / 2 - 1;
            L -=  n % 2 == 0 ? counter / 2 : (counter - 1) / 2;
            R =   n - 1 - L;
            n =   L;
            std::cout << "counter = "
                      << counter
                      << '\t'
                      << "L = "
                      << L
                      << '\t'
                      << "R = "
                      << R
                      << std::endl;
 
        }while(n > counter + 1);     
    }
    return  counter;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        int  n = 0; 
        std::cout << std::endl
                  << std::endl
                  << "n = ";
 
        std::cin >> n;
        std::cout << "Итого "
                  << get_unlinks_min(n)
                  << " расцеплений."
                  << std::endl;
    }    
}
1
nicolaus2
19 / 19 / 3
Регистрация: 11.07.2010
Сообщений: 63
06.04.2011, 11:20  [ТС] 9
Mr.X, прошу прощения, вчера день сложный был, неправильно написал( У Вас ответ верный - 12.

Добавлено через 6 минут
У вас считает абсолютно точно. Не поделитесь коротким описанием идеи?

Добавлено через 4 минуты
C++
1
L = n / 2 * 2 / 2 - 1;
можно вполне заменить на
C++
1
 L =   n / 2 - 1;
0
Mr.X
Эксперт С++
3188 / 1715 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
06.04.2011, 11:57 10
Цитата Сообщение от nicolaus2 Посмотреть сообщение
C++
1
L = n / 2 * 2 / 2 - 1;
можно вполне заменить на
C++
1
L = n / 2 - 1;
Да, это я что-то погорячился, видать у меня вчера тоже был сложный день.
Цитата Сообщение от nicolaus2 Посмотреть сообщение
Не поделитесь коротким описанием идеи?
Ну, идея здесь простая: если расположить длины кусков по возрастанию, то в этом ряду каждое число,
не равное единице, не должно превосходить сумму предшествующих больше чем на единицу.
1
nicolaus2
19 / 19 / 3
Регистрация: 11.07.2010
Сообщений: 63
06.04.2011, 12:12  [ТС] 11
После прочтения задачи первое что пришло в голову - числа Фибоначчи, второе - что-то связанное с делением пополам. Оба метода давали близкие результаты, но не те. А у вас что-то вроде и того и другого.

Спасибо за решение.

Еще, зачем вы на каждом шаге отнимаете при четном значении n?
C++
1
L -=  n % 2 == 0 ? counter / 2 : (counter - 1) / 2;
0
Mr.X
Эксперт С++
3188 / 1715 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
06.04.2011, 12:22 12
Цитата Сообщение от nicolaus2 Посмотреть сообщение
Еще, зачем вы на каждом шаге отнимаете при четном значении n?
C++
1
L -= n % 2 == 0 ? counter / 2 : (counter - 1) / 2;
Да нет, здесь отнимается при любом n, только при четном counter / 2, а при нечетном (counter - 1) / 2.
Собственно, этот оператор и обеспечивает выполнение условия, приведенного мной в предыдущем сообщении.
1
nicolaus2
19 / 19 / 3
Регистрация: 11.07.2010
Сообщений: 63
06.04.2011, 12:47  [ТС] 13
Вот теперь то я все понял. Отличная идея! Откуда она берет истоки? Т.е. почему такая закономерность верна?
0
Mr.X
Эксперт С++
3188 / 1715 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
06.04.2011, 14:39 14
Цитата Сообщение от nicolaus2 Посмотреть сообщение
Вот теперь то я все понял. Отличная идея! Откуда она берет истоки? Т.е. почему такая закономерность верна?
Ну, если мы имеем n кусков длиной 1, то можем получить из них любую цепочку длиной от 1 до n, следовательно первый неединичный кусок должен иметь длину k <= (n + 1), иначе мы цепочку такой длины никак не получим.
Добавляя этот кусок к предыдущим комбинациям, получаем все цепочки длиной от 1 до (n + k).
Рассуждая аналогично, получаем, что следующий кусок должен иметь длину m <= (n + k) + 1, и так далее.

Добавлено через 1 час 21 минуту
Если уж совсем упростить, то вот так можно записать:
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
50
51
52
53
54
55
56
57
58
/////////////////////////////////////////////////////////////////////////////////////////
//Допустим, есть цепочка длины N. Сколько минимум колец нужно расцепить, чтобы из кусков 
//можно было получить любую цепочку длины от 1 до N. Расцеплением считать не разрыв цепочки, 
//а деление ее путем отделение одного кольца.
//
//Например, для цепочки 21 нужно минимум 2 таких расцепление. Мы получим цепочки 
//длинной 1, 1, 3, 5, 11 и можем сложить цепочку длинной от 1 до N.
//
//Есть хотя бы идеи каков алгоритм решения этой задачи?
//
//P.S.
//Еще примеры, первое - длина цепочки, второе - минимальное количество расцеплений.
//7 - 1
//8 - 2
//21 - 2
//24 - 3
//159 - 4
//160 - 5
//384 -6
//2047 - 7
//10239 - 9
//49152 - 12
//...
//1 000 000 000 - 25 
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
int  get_unlinks_min(int  n)
{
    int  counter  = 0;    
    
    if(n > 1)
    {
        do
        {           
            n /= 2;
        }while(n > ++counter * 2 + 1);     
    }
    return  counter;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        int  n = 0; 
        std::cout << std::endl
                  << std::endl
                  << "n = ";
 
        std::cin >> n;
        std::cout << "Всего "
                  << get_unlinks_min(n)
                  << " расцеплений."
                  << std::endl;
    }    
}
2
GHooST
0 / 0 / 0
Регистрация: 10.02.2015
Сообщений: 6
08.04.2011, 19:12 15
А как поступить в том случае, если цепочка закольцована? Получается похожий алгоритм, но никак не могу вывести правильный.
0
Mr.X
Эксперт С++
3188 / 1715 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
09.04.2011, 15:56 16
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/////////////////////////////////////////////////////////////////////////////////////////
//А как поступить в том случае, если цепочка закольцована?
/////////////////////////////////////////////////////////////////////////////////////////
//<ОПИСАНИЕ ЗАДАЧИ ДЛЯ НЕЗАКОЛЬЦОВАННОЙ ЦЕПОЧКИ>
//Допустим, есть цепочка длины N. Сколько минимум колец нужно расцепить, чтобы из кусков 
//можно было получить любую цепочку длины от 1 до N. Расцеплением считать не разрыв цепочки, 
//а деление ее путем отделение одного кольца.
//
//Например, для цепочки 21 нужно минимум 2 таких расцепление. Мы получим цепочки 
//длинной 1, 1, 3, 5, 11 и можем сложить цепочку длинной от 1 до N.
//
//Есть хотя бы идеи каков алгоритм решения этой задачи?
//
//P.S.
//Еще примеры, первое - длина цепочки, второе - минимальное количество расцеплений.
//7 - 1
//8 - 2
//21 - 2
//24 - 3
//159 - 4
//160 - 5
//384 -6
//2047 - 7
//10239 - 9
//49152 - 12
//...
//1 000 000 000 - 25 
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
int  get_unlinks_min(int  n)
{
    int  counter  = 1;    
    
    while(n > counter * 2 + 1)
    {           
        ++counter;
        n /= 2;
    }     
 
    return  counter;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    const int  LEN_MIN = 3;
    for(;;)
    {
        int  n = 0; 
        do
        {
            std::cout << "Введите длину кольцевой цепочки >= "
                      << LEN_MIN
                      << ": ";
 
            std::cin >> n;        
        }while(n < LEN_MIN);
 
        std::cout << "Всего "
                  << get_unlinks_min(n)
                  << " расцеплений."
                  << std::endl
                  << std::endl                     
                  << std::endl;
    }    
}
1
GHooST
0 / 0 / 0
Регистрация: 10.02.2015
Сообщений: 6
09.04.2011, 16:10 17
Спасибо большое. Я пошёл по другому пути. Может кому пригодится.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
int main()
{
    long long n=0,fl=1,l=0,r=0,min=1;
    scanf("%I64d",&n);
    while(n && n!=3)
    {
         fl*=2;
         l=( fl*(min+1) )-1;
         r=( fl*2*(min+2) )-1; 
         ++min;  
         if( n<=r && n>l )
         {
              printf("%I64d",min);
              return 0;
         }
    }
    if(n==3)
    {
        printf("%I64d",min);
        return 0;
    }
}

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
09.04.2011, 16:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.04.2011, 16:10

Загрузка из файла 64-разрядного целого числа и разбивка его на 4-16 разрядных
Добрый день, Подскажите пожалуйста есть ли возможность средствами С++ загрузить из csv файла в...

При вводе значения идет разбивка числа на разряды, а курсор перемещается влево
Всем привет. Использую тут StringFormat для отображения числа как &quot;денежку&quot;. &lt;DataGridTextColumn...

Разбивка на страницы
Подскажите как быть. Сделал вывод пользователей по страницам. Стоит сортировка по дате...


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

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

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