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

Задачка - крепкий орешек про линейку - C++

Восстановить пароль Регистрация
 
lancoma
0 / 0 / 0
Регистрация: 30.10.2012
Сообщений: 11
10.11.2012, 16:32     Задачка - крепкий орешек про линейку #1
Никак не могу разобраться с задачкой. Скажу сразу, что она хоть и для новичков - программистов, но считается сложной, олимпиадной.
Длина линейки M см. Слава, на отметке 0 размещен ползунок, который в итоге должен переместиться на конец правой стороны (на отметку M). Ползунок может совершать только перемешения определенных размеров и только вперед (вправо).

Например, если M=3 и разрешено перемещаться на отрезки 1 и 2, то ползунок может добраться до отметки 3 тремя разными способами: 1-1-1; 1-2; 2-1.

Значение M(длина линейки) и значения S(кол-во разных отрезков) вводит пользователь. Известно, что M должно быть меньше или равно 30, а S <=5. Когда будет введено S, у пользователя попросят ввести несколько натуральных чисел - длин отрезков. Причем, каждый отрезок должен быть больше нуля и меньше или равен M.

В результате на экран должно быть выведено целое число - кол-во разных способов, которыми ползунок может может добраться до отметки M.
Даже не знаю, как эту задачу решать и уж тем более запрограммировать... Там ведь столько возможных вариантов... Программировать нужно в C++. Помогите, пожауйста, кто чем сможет!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2012, 16:32     Задачка - крепкий орешек про линейку
Посмотрите здесь:

C++ Задачка про массивы
Задачка про последовательность. C++
C++ Задачка про двумерные массивы
C++ Задачка про треугольник.
задачка про ящики C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
leopardile
5 / 5 / 0
Регистрация: 10.07.2011
Сообщений: 15
10.11.2012, 18:23     Задачка - крепкий орешек про линейку #2
Интересная задача) Я вот так решил. Новичок, за нерациональность не пеняйте)

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
#include <iostream>
 
using namespace std;
 
int ways_number(int M);
int * ar;
int S;
 
int main(){
    int M;
    
    cout<<"M: ";
    cin>> M;
    cout<<"S: ";
    cin>> S;
 
    ar = new int[S];
    for(int i=0; i<S; i++){
        cin>>ar[i];
    }
 
    cout<<"Answer: "<<ways_number(M)<<endl;
 
    system("pause");
    return 0;
}
 
int ways_number(int M){
    int res=0;
    for(int i=0; i<S; i++){
        if(ar[i]==M) res++;
        if(ar[i]<M) res+=ways_number(M - ar[i]);
    }
    return res;
}
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.11.2012, 21:24     Задачка - крепкий орешек про линейку #3
Вот, почитайте тут
http://www.intuit.ru/department/algo...combi/5/2.html
Как эту же задачу можно было сделать без рекурсивного прямого перебора. Т.е. быстрее
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
10.11.2012, 21:34     Задачка - крепкий орешек про линейку #4
М целое и <=30?
Используй ДП!
Заведи массив из M элементов и в каждый, записывай количество способов, какими можно до него добраться.

количество путей в i-й элемент есть сумма количества путей в элементы i-1, i-2, ... ,i-S
В итоге, найдёшь путь, стоящий меньше всего денег
-=ЮрА=-
Заблокирован
Автор FAQ
10.11.2012, 22:07     Задачка - крепкий орешек про линейку #5
lancoma, вот мой взгляд на проблему
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
#include <ctime>
#include <vector>
#include <cstdlib>
#include <iostream>
using namespace std;
 
//ÔóГ*êöèÿ âîçâðГ*Г№Г*ГҐГІ îñòГ*òîê îò Г°Г*Г§Г*îñòè ГЊ ГЁ ñóììû îòåðêçîâ
//Г*Г*ëè÷èå ýòîé ГґГіГ*êöòò ïîçâîëèò ïðîèçâåñòè ââîä Г°Г*Г§Г*ûõ îòðåçêîâ
//ñóììГ* êîòîðûõ Г¤Г*Г±ГІ M
int calcRestLength(int M, vector <int> parts, int restNum);
 
int main()
{
    int i, j;//Ñ÷¸ò÷èêè
    int part;//ÄëèГ*Г*Г* îòäåëüГ*îé Г·Г*Г±ГІГЁ
    int count = 0;//Ñ÷¸ò÷èê ГЇГіГҐГ©
    int length;//äëèГ*Г*Г* ñóììû îòðåçêîâ
    int N = 0;//Áóäåò ñîäåðæГ*ГІГј Гў Г±ГҐГЎГҐ ÷èñëî ГўГ*ðèГ*Г*òîâ êîòîðûìè ìîæГ*Г® äîáðГ*ГІГјГ±Гї äî ГЊ
    srand(time(0));//ГіГ±ГІГ*Г*îâèëè Г*Г*Г· Г§Г*Г*Г·ГҐГ*ГЁГҐ Гў ГЈГҐГ*ГҐГ°Г*òîðå ñëó÷ Г·ГЁГ±ГҐГ«
    //Èìåòèðóåì ââîä ïîëüçîâГ*òåëÿ
    int S = 5; //ìîæГ*Г® áûëî ГЎГ» ðåГ*ëèçîâГ*ГІГј ГЄГ*ГЄ S = 1 + rand()%5
    int M = 30;//30 ïîóñëîâèþ Г*Гі ГЁ áîã Г± Г*ГЁГ¬, õîòÿ ìîæГ*Г® äëèГ*Гі ëèГ*åéêè ГЁ Г°Г*Г*äîìГ*Г® ñäåëГ*ГІГј
    vector <int> parts;//Âåêòîð Г± äëèГ*Г*ìè îòðåçêîâ
    for(i = 0; i < S; i++)
    {
        //Г‡Г*ïîëГ*ГїГҐГ¬ âåêòîð Г·Г*ñòÿìè áîëüøå Г*óëèÿ ГЁ <= M
        part = calcRestLength(M, parts, S - (i + 1));
        cout<<"Length of "<<i + 1<<" part : "<<part<<endl;
        parts.push_back(part);
    }
    //Г’Г*ГЄГ± Г* òåïåðü ïîåõГ*ëè ГЁГ±ГЄГ*ГІГј ñïîñîáû äîñòèæåГ*ГЁГї ГЄГ®Г*Г¶Г* ëèГ*åéêè
    cout<<"Roots searching start..."<<endl;
    for(i = 0; i < S; i++)
    {
        cout<<"Current Root : "<<parts[i];
        length = parts[i];
        for(j = 0; j < S && length < M; j++)
        {
            if(i != j)
            {
                length += parts[j];
                cout<<" - "<<parts[j];
            }
        }
        cout<<"\nM acceded Root lenth : "<<length<<endl;
        if(M != length)
        {
            cout<<"Root length = "<<length<<endl;
            cout<<"M != length - root not acepted"<<endl;
        }
        else
        {
            cout<<"M == length - root acepted"<<endl;
            count++;
        }
    }
    cout<<"Roots searching end"<<endl;
    cout<<"Total number of roots : "<<count<<endl;
    cin.get();//Ñòîï òî÷êГ*
    return 0;
}
 
int calcRestLength(int M, vector <int> parts, int restNum)
{
    int i;
    int length = 0;
    int count  = 0;
    for(i = 0; i < (int)parts.size(); i++)
        length += parts[i];
    for(i = 0; i < restNum; i++)
        count += (i + 1);
    return 1 + rand()%(M - length - count + 1);
}
Проверка здесь http://codepad.org/oLGmJkbQ
Кликните здесь для просмотра всего текста
Length of 1 part : 14
Length of 2 part : 5
Length of 3 part : 1
Length of 4 part : 2
Length of 5 part : 1
Roots searching start...
Current Root : 14 - 5 - 1 - 2 - 1
M acceded Root lenth : 23
Root length = 23
M != length - root not acepted
Current Root : 5 - 14 - 1 - 2 - 1
M acceded Root lenth : 23
Root length = 23
M != length - root not acepted
Current Root : 1 - 14 - 5 - 2 - 1
M acceded Root lenth : 23
Root length = 23
M != length - root not acepted
Current Root : 2 - 14 - 5 - 1 - 1
M acceded Root lenth : 23
Root length = 23
M != length - root not acepted
Current Root : 1 - 14 - 5 - 1 - 2
M acceded Root lenth : 23
Root length = 23
M != length - root not acepted
Roots searching end
Total number of roots : 0

как видим очень сильное влияние на резултат оказывает длинна вводимых отрекзков, нужны какие то оп критери. Поясню - мы можем считать что достигли конца если скажем имея 30 см линейку и отрезки 12 + 10 + 15 получим длинну маршрута 37. Но мне кажется нужно точное совпадение длин, т.е на ввод отрезков должно отражаться правило что хотябы из двух из них можно было бы получить набор сумм равный длине линейки. Я попытался поставить такое ограничение на ввод, но всё же если есть такая возможность хотел бы увидеть доп критерии на длину вводимых отрезков
Миниатюры
Задачка - крепкий орешек про линейку  
lancoma
0 / 0 / 0
Регистрация: 30.10.2012
Сообщений: 11
10.11.2012, 22:45  [ТС]     Задачка - крепкий орешек про линейку #6
leopardile, вы знаете, я когда в вашей программе ввожу S, то ввожу их сколько угодно (процесс не прекращается) и какого угодно размера. А их должно быть не более 5 и длиной не более 30.

-=ЮрА=-, у вас код прям какой-то очень умный и большой, а я еще совсем-совсем новичок, и мы ctime не используем. Можно как-то совсем по-простому, может, даже не совсем рационально?
leopardile
5 / 5 / 0
Регистрация: 10.07.2011
Сообщений: 15
11.11.2012, 01:40     Задачка - крепкий орешек про линейку #7
Цитата Сообщение от lancoma Посмотреть сообщение
leopardile, вы знаете, я когда в вашей программе ввожу S, то ввожу их сколько угодно (процесс не прекращается) и какого угодно размера. А их должно быть не более 5 и длиной не более 30.
S - это ведь количество длин отрезков, или я что-то неправильно понял? По идее, вы вводите S, в промежутке [1,5], а потом вводите еще S значений, длины этих отрезков. По крайней мере, у меня все работает)
Если хотите, можете ввести проверку S, M и всех введенных значений длин, это ведь совсем несложно)
lancoma
0 / 0 / 0
Регистрация: 30.10.2012
Сообщений: 11
11.11.2012, 01:47  [ТС]     Задачка - крепкий орешек про линейку #8
Цитата Сообщение от leopardile Посмотреть сообщение
S - это ведь количество длин отрезков, или я что-то неправильно понял? По идее, вы вводите S, в промежутке [1,5], а потом вводите еще S значений, длины этих отрезков. По крайней мере, у меня все работает)
Если хотите, можете ввести проверку S, M и всех введенных значений длин, это ведь совсем несложно)
А у меня не работает. Я и М=40 смогла ввести, и S=6. Так быть не должно.
leopardile
5 / 5 / 0
Регистрация: 10.07.2011
Сообщений: 15
11.11.2012, 03:28     Задачка - крепкий орешек про линейку #9
lancoma, я добавил проверки) Я так понимаю, только в них проблема была?
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
#include <iostream>
 
using namespace std;
 
int ways_number(int M);
int * ar;
int S;
 
int main(){
    int M;
    
    cout<<"M: ";
    cin>> M;
    while(M<=0||M>30){
        cout<<"Wrong value. Try Again: ";
        cin>>M;
    }
 
    cout<<"S: ";
    cin>> S;
    while(S<=0||S>5){
        cout<<"Wrong value. Try Again: ";
        cin>>S;
    }
 
    ar = new int[S];
    for(int i=0; i<S; i++){
        cin>>ar[i];
        while(ar[i]<=0||ar[i]>M){
            cout<<"Wrong value. Try Again: ";
            cin>>ar[i];
        }
    }
 
    cout<<"Answer: "<<ways_number(M)<<endl;
 
    system("pause");
    return 0;
}
 
int ways_number(int M){
    int res=0;
    for(int i=0; i<S; i++){
        if(ar[i]==M) res++;
        if(ar[i]<M) res+=ways_number(M - ar[i]);
    }
    return res;
}
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
11.11.2012, 04:02     Задачка - крепкий орешек про линейку #10
А вот мой взгляд на эту проблему:
Допустим ради примера, что надо найти сколькими способами можно перейти на линейке, имеющей длину 30 см, излевого конца в правый, двигаясь шагами в 2, 5 и 7 см. Конкретные цифры взяты для краткости.

Тогда комбинаторика говорит нам, что для этого достаточно составить вот такую функцию:
1 / [(1 + x^2) * (1 + x^5) * (1 + x^7)], далее разделить это столбиком по возрастающим степеням x и найти значение коэффициента при x^30.

Все просто, как три рубля.
leopardile
5 / 5 / 0
Регистрация: 10.07.2011
Сообщений: 15
11.11.2012, 04:10     Задачка - крепкий орешек про линейку #11
ramybozy, интересно А можно чуть-чуть подробнее, с примером кода?
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
11.11.2012, 04:12     Задачка - крепкий орешек про линейку #12
Да никакого кода тут нет.
Я вам точное решение привел.
Ну если хотите, то займитесь программированием деления многочленов столбиком.
Но это уже отдельная тема.
leopardile
11.11.2012, 04:27
  #13

Не по теме:

ramybozy, у меня лично с матчастью этого решения проблема, 10-й класс же, не проходили такого
Но это мои проблемы, конечно)

ramybozy
11.11.2012, 04:35
  #14

Не по теме:

Да, конечно, не проходили.
Но это же не значит, что любую задачу, которую не может решить продвинутый десятиклассник, надо сразу решать с использованием программирования.

I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
11.11.2012, 04:39     Задачка - крепкий орешек про линейку #15
ramybozy, ваш способ равносилен прямому перебору. И вы это поймете, если задумаетесь над его реализацией. Динамическое программирование - вот решение. Я уже кидал ссылку на объяснение.
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
11.11.2012, 04:42     Задачка - крепкий орешек про линейку #16
Да ну,
Первый раз слышу, что деление столбиком двух многочленов, как то соотносится с динамическим программированием.

Не по теме:

Да и еще, это не мой метод, я не такой умный, чтобы мне можно было приписать методику использования производящих функций.

Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
11.11.2012, 04:45     Задачка - крепкий орешек про линейку #17
Цитата Сообщение от ramybozy Посмотреть сообщение
Да ну,
Первый раз слышу, что деление столбиком двух многочленов, как то соотносится с динамическим программированием.
По-моему, он сказал, что способ соотносится не с ДП, а с прямым перебором.
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
11.11.2012, 04:59     Задачка - крепкий орешек про линейку #18
Тогда тем более.
Никакого перебора тут нет, а есть прямой способ найти заданный ответ.
Если деление столбиком двух многочленов вызывает такие мучительные проблемы, то обращайтесь к книге Новоселова "Элементарная алгебра" (стр. 86).
Взять можно тут: http://www.diary.ru/~eek/p179947910.htm?oam
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.11.2012, 07:53     Задачка - крепкий орешек про линейку #19
Цитата Сообщение от ramybozy Посмотреть сообщение
Тогда тем более.
Никакого перебора тут нет, а есть прямой способ найти заданный ответ.
Вам не говорят что Ваш способ неправильно считает. Просто считает неоптимально по времени.
ramybozy, Введите например: 30, 5, 1, 2, 3, 4, 5 и посмотрите как долго считает Ваша программа.
Если использовать ДП, то будет считать любой тест менее 1 сек.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2012, 17:58     Задачка - крепкий орешек про линейку
Еще ссылки по теме:

Задачка про Барона Мюнхгаузена C++
Задачка про спорт C++

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

Или воспользуйтесь поиском по форуму:
leopardile
5 / 5 / 0
Регистрация: 10.07.2011
Сообщений: 15
11.11.2012, 17:58     Задачка - крепкий орешек про линейку #20
Я так понимаю, мою функцию в коде выше можно так оптимизировать?
C++
1
2
3
4
5
6
7
8
9
10
11
int ways_number(int M){
    int * res=new int[M+1];
    for(int i=1; i<=M; i++){
        res[i]=0;
        for(int j=0;j<S;j++){
            if(i==ar[j]) res[i]++;
            if(i>ar[j]) res[i] += res[i-ar[j]];
        }
    }
    return res[M];
}
Yandex
Объявления
11.11.2012, 17:58     Задачка - крепкий орешек про линейку
Ответ Создать тему
Опции темы

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