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

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

Войти
Регистрация
Восстановить пароль
 
 
lancoma
0 / 0 / 0
Регистрация: 30.10.2012
Сообщений: 11
#1

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

10.11.2012, 16:32. Просмотров 819. Ответов 19
Метки нет (Все метки)

Никак не могу разобраться с задачкой. Скажу сразу, что она хоть и для новичков - программистов, но считается сложной, олимпиадной.
Длина линейки 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++. Помогите, пожауйста, кто чем сможет!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2012, 16:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задачка - крепкий орешек про линейку (C++):

Задачка про треугольник. - C++
Для вас эта задача очень легкая, но я не как не могу ее сделать. Пожалуйста помогите! Условие такое : В треугольнике (см. рис. 1.8,...

Задачка про массивы - C++
Только начала изучать программирование, пытаюсь разбиратся ,но не всё так просто , помогите пжлст решить задачку на массивы Даны два...

Задачка про спорт - C++
Вводятся фамилии спортсменов и их результаты в соревнованиях по прыжкам в длину. После ввода данных очередного спортсмена выводить...

задачка про ящики - C++
Имеется 8 ящиков у всех вес по 2 кг, а у одного 1 кг, записать это все в массив и определить в каком по номеру элементе массива содержится...

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

Задачка про Коня и Короля - C++
Задана шахматная доска, на которой расставлены черные и белые фигуры, в том числе белый король и черный конь. Определить, может ли белый...

19
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;
}
1
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.11.2012, 21:24 #3
Вот, почитайте тут
http://www.intuit.ru/department/algorithms/algocombi/5/2.html
Как эту же задачу можно было сделать без рекурсивного прямого перебора. Т.е. быстрее
1
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
10.11.2012, 21:34 #4
М целое и <=30?
Используй ДП!
Заведи массив из M элементов и в каждый, записывай количество способов, какими можно до него добраться.

количество путей в i-й элемент есть сумма количества путей в элементы i-1, i-2, ... ,i-S
В итоге, найдёшь путь, стоящий меньше всего денег
1
-=ЮрА=-
Заблокирован
Автор 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. Но мне кажется нужно точное совпадение длин, т.е на ввод отрезков должно отражаться правило что хотябы из двух из них можно было бы получить набор сумм равный длине линейки. Я попытался поставить такое ограничение на ввод, но всё же если есть такая возможность хотел бы увидеть доп критерии на длину вводимых отрезков
1
Миниатюры
Задачка - крепкий орешек про линейку  
lancoma
0 / 0 / 0
Регистрация: 30.10.2012
Сообщений: 11
10.11.2012, 22:45  [ТС] #6
leopardile, вы знаете, я когда в вашей программе ввожу S, то ввожу их сколько угодно (процесс не прекращается) и какого угодно размера. А их должно быть не более 5 и длиной не более 30.

-=ЮрА=-, у вас код прям какой-то очень умный и большой, а я еще совсем-совсем новичок, и мы ctime не используем. Можно как-то совсем по-простому, может, даже не совсем рационально?
0
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 и всех введенных значений длин, это ведь совсем несложно)
0
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. Так быть не должно.
0
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;
}
1
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.

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

Не по теме:

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

0
ramybozy
11.11.2012, 04:35
  #14

Не по теме:

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

0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
11.11.2012, 04:39 #15
ramybozy, ваш способ равносилен прямому перебору. И вы это поймете, если задумаетесь над его реализацией. Динамическое программирование - вот решение. Я уже кидал ссылку на объяснение.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2012, 04:39
Привет! Вот еще темы с ответами:

Задачка про Барона Мюнхгаузена - C++
Барон Мюнхаузен, выйдя на экологически чистую охоту, зарядил свое ружье косточками вишен. После того как он удачно попал между рога оленям,...

Задачка про кривые Безье - C++
Нужны советы (скорее алгоритмические) по одной задаче. Даны опорные точки кривой Безье, начальный и конечный параметры t0 и t1(0&lt;t&lt;1), а...

Задачка про деревья на рекурсию - C++
Пасаны, не особо шарю деревья, а еще нужно рекурсия.. Короче нужна помощь, хотя бы объеснить что как должно работать, буду очень...

Задачка про строки и слова - C++
Ошибочка закралась: суть задачки надо прочитать файл и вывести слова которые начинаются и кончаются на &quot;a&quot; (ну вот вбил я в свой файл для...


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

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

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