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

Перебор - C++

Восстановить пароль Регистрация
 
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 19:39     Перебор #1
Hi.мне нужно часть кода в котором перебирает все значение
пример
у нас 2 банки(на много литров),и 10 л воды.Нужно сделать все возможние перелитие воды с 1 банки во 2.(банка не может быть пустой).
банка_1(кол л.) банка_2(кол л.)
1(1) 2(9)
1(2) 2(8)
1(3) 2(7)
1(4) 2(6)
1(5) 2(5)
1(6) 2(4)
1(7) 2(3)
1(8) 2(2)
1(9) 2(1)
вот так на 2 банки с 10л
а как мне сделать на на 4 банки с 20л.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2013, 19:39     Перебор
Посмотрите здесь:

C++ Перебор комбинаций
C++ Перебор чисел
Перебор C++
Перебор текста C++
Cудоку перебор C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
11.12.2013, 19:42     Перебор #2
C++
1
2
for (int i = 1; i < 10; i++)
     printf("1(%d) 2(%d)\n",i,10-i)
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 19:44  [ТС]     Перебор #3
Цитата Сообщение от newyork7776 Посмотреть сообщение
а как мне сделать на на 4 банки с 20л.
вопрос вот

Добавлено через 1 минуту
с 4 цыклами там задание решить нельзя
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.12.2013, 19:46     Перебор #4
Цитата Сообщение от newyork7776 Посмотреть сообщение
с 4 цыклами там задание решить нельзя
это вопрос или утверждение?
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 19:48  [ТС]     Перебор #5
ValeryS,
Цитата Сообщение от ValeryS Посмотреть сообщение
утверждение
Добавлено через 37 секунд
у нас эсть N банок и M кол л. воды
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.12.2013, 19:52     Перебор #6
C++
1
2
3
4
for(int i=1;i<18;i++)
 for(int j=1;j<20-1-i;j++)
  for(int k=1;k<20-i-j;k++)
    printf("%d %d %d %d",i,j,k,20-i-j-k)
примерно так, но не проверял

Добавлено через 41 секунду
newyork7776,
тебе нужны комбинации или количество комбинаций?
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 19:54  [ТС]     Перебор #7
ValeryS,
Цитата Сообщение от ValeryS Посмотреть сообщение
нужны комбинации
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.12.2013, 19:56     Перебор #8
тогда я не знаю как без циклов вывести все комбинации
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 20:00  [ТС]     Перебор #9
не наверное задание я криво обяснил
у нас есть N банок и M л. воды.Нужно написать все возможные варианты.
А без цикла здесь решить невозможно.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.12.2013, 20:35     Перебор #10
Цитата Сообщение от newyork7776 Посмотреть сообщение
у нас есть N банок и M л. воды.
количество банок и воды заранее не известно?
чувствую здесь рекурсию, но пока нащупать не могу
типа такого
количество комбинаций в N банках равна N - M умноженную на количество комбинаций N -1 M-1 л. воды
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 20:44  [ТС]     Перебор #11
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
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n,m,q,a,b;
    vector <int> v;
    cin >> n >> m;
    for(int i=0;i<m;i++){v.push_back(1);};
    q=(abs(n-m)+1);
    v[m-1]=q;
    a=m-1;
    b=m-2;
    while (v[0]!=q)
    {
        for(int i=0;i<m;i++)
        {cout << v[i] << " ";};
        cout << "\n";
        if (v[a]!=1)
        {
            v[a]--;
            v[b]++;
        }
        else 
        {
            a--;
            b--;
        };
    };
    for(int i=0;i<m;i++)
        {cout << v[i] << " ";};
        cout << "\n";
    system("pause");
}
вот решил

Добавлено через 34 секунды
нормально или нет?

Добавлено через 4 минуты
нет не то
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.12.2013, 20:46     Перебор #12
Цитата Сообщение от newyork7776 Посмотреть сообщение
q=(abs(n-m)+1);
вот здесь abs по моему лишний
если количество банок больше количества воды то задача не решаема, нельзя 2 литра разлить на 10 банок
значит
q=m-n+1;
и если q отрицательно или равно нулю то задача не имеет решений
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 20:51  [ТС]     Перебор #13
ValeryS, то мелочи
мне нужно как-то сделать что-бы оно не только соседнее счетало но и переносило 1 на пред елемент масива и заново счетало

Добавлено через 2 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
10
3
1 1 8
1 2 7
1 3 6
1 4 5
1 5 4
1 6 3
1 7 2
1 8 1
1 8 1
2 7 1
3 6 1
4 5 1
5 4 1
6 3 1
7 2 1
8 1 1
нужно убрать 10 или 11 строку
+
12,13,14... смотрит только на 1 та 2 число а не на 2,3
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.12.2013, 21:54     Перебор #14
Цитата Сообщение от newyork7776 Посмотреть сообщение
мне нужно как-то сделать что-бы оно не только соседнее счетало но и переносило 1 на пред елемент масива и заново счетало
так вот это то и есть самое главное
если количество банок неизвестно на момент программирования то не можешь задать количество циклов
а как сделать разное количество циклов я не знаю(точнее не придумал еще), вот и вертится в голове рекурсия

Добавлено через 1 час 1 минуту
держи вот что то накропал

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
#include <iostream>
#include <vector>
using namespace std;
void fnc( vector <int> a,int N,int M, int i)
{
 
 
 if(M<2)
  {
   for(int j=0;j<a.size()-1;j++)
   {
       printf("%d ",a[j]);
   }
     printf("%d ",N);
     printf("\n ");
   return;
  }
  a[i]++;
  for(int j=a[i];j<=N-M+1;j++)
   {
    fnc(a,N-a[i],M-1,i+1);
     a[i]++;
     
   } 
}
 
int main()
{
    int n,m;
    vector <int> v;
    cin >> n >> m;
    for(int i=0;i<m;i++){v.push_back(0);};
    fnc(v,n,m,0);
    
    system("pause");
    return 0;
}
до 4 проверил а дальше нет слишком много текста
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 23:10  [ТС]     Перебор #15
ValeryS, а можна перевести в с++.я просто с не очень понимаю."%d "
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2013, 23:21     Перебор
Еще ссылки по теме:

Перебор значений C++
Полный перебор C++
Оптимизировать перебор C++

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
11.12.2013, 23:21     Перебор #16
Цитата Сообщение от ValeryS Посмотреть сообщение
if(M<2)
{
for(int j=0;j<a.size()-1;j++)
{
printf("%d ",a[j]);
}
printf("%d ",N);
printf("\n ");
return;
}
C++
1
2
3
4
5
6
7
8
if(M<2)// если ведро последнее
 {
  for(int j=0;j<a.size()-1;j++)
      cout<<a[j];  // то выводим весь вектор на экран кроме последнего элемента
 
   cout<<N<<endl;  // в качестве последнего элемента выводим остаток
  return;
 }
можно так
C++
1
2
3
4
5
6
7
8
9
if(M<2)// если ведро последнее
 {
  a[i]=N; в последний элемент вектора остаток воды
   for(int j=0;j<a.size();j++)
       cout<<a[j];  // то выводим весь вектор на экран
 
  cout<<endl;  //перевод строки для новой комбинации
  return;
   }
там наверно еще можно где улучшить, это так мысли вслух
Цитата Сообщение от newyork7776 Посмотреть сообщение
не очень понимаю."%d "
вывести в десятичном виде
мне printf больше нравится он более гибкий чем cout
Yandex
Объявления
11.12.2013, 23:21     Перебор
Ответ Создать тему
Опции темы

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