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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
#1

Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм - C++

17.01.2013, 13:05. Просмотров 1518. Ответов 13
Метки нет (Все метки)

Имееться 10 гирь весом 100 200 300 500 1000 1200 1400 1500 2000 3000 грамм каждая. Сколькими способами гирями этого набора можно составить вес в v грамм.
Вот собственно к чему пришел, но не правильно. Помогите!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int v,vv,count=0;       //zlatopol 8.47
int g[10]={100,200,300,500,1000,1200,1400,1500,2000,3000};
cin>>v;
vv=v;
for (int j=9;j>=0;j--)
{
vv=v;
if (g[j]>vv) continue;
vv-=g[j];
if (vv==0) {count++;vv+=g[j];}
for (int i=j-1;i>=0;i--)
{
    if (g[i]>vv) continue;
    vv-=g[i];
    if (vv==0) {count++;vv+=g[i];}
}
}
 
cout<<count<<endl;
 
return 0;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.01.2013, 13:05     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм
Посмотрите здесь:
Комбинаторика: сколькими способами можно отправить на олимпиаду 3 из 17 учеников? C++
Сколькими возможными способами можно рассадить на n стульев n человек? C++
C++ Определить сколькими различными способами можно подняться на десятую ступеньку
C++ Требуется вычислить сколькими способами можно получить строку В из строки А
Определить сколькими различными способами можно подняться на заданную ступеньку (Лестница в Небо) C++
C++ Сколькими способами можно изменить заданную последовательность, чтобы она осталась возрастающей?
Составить программу для сортировки данного набора строк по символу C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
18.01.2013, 23:18  [ТС]     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #2
Т.е. в нашем расположении только по одной гире указанных весов. Т.е.
1500=1500
1500=1400+100
1500=1200+300
1500=1200+200+100
1500=1000+500
1500=1000+300+200

Добавлено через 4 часа 24 минуты
Все, больше не знаю куда дальше. Некоторые правильно считает, некоторые нет. Скоро лопнет голова. Может я вообще не в те дебри полез?!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int v,vv,count=0;       //zlatopol 8.47
int g[10]={100,200,300,500,1000,1200,1400,1500,2000,3000};
cin>>v;
vv=v;
for (int j=9;j>=0;j--)
{
    vv=v;
    if (g[j]>vv) continue;
for (int i=j;i>=0;i--)
{
    if (g[i]>vv) continue;
for (int k=j;k>=0;k--)
{
    if (g[k]>vv) continue;
    vv-=g[k];
    if (vv==0) {count++; break;}
}
    if (vv==0) continue;
}
    if (vv==0) continue;
}
 
cout<<count<<endl;
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
18.01.2013, 23:24     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #3
гугли динамическое программирование.
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 00:19  [ТС]     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #4
Да рано вроде еще. Только начали учить си. Но все равно спасибо за совет!
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
19.01.2013, 00:32     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #5
Ну так и задача не совсем для чайников.
Тогда такой способ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N=10;
int g[10]={100,200,300,500,1000,1200,1400,1500,2000,3000};
int main(){
  int mask, sum, bit, count=0;
  int v;
  cin>>v; 
  for (int i=1; i<=0x3FF;i++){
    mask=1, sum=bit=0;
    while(mask<=i){
      if(i&mask) sum+=g[bit];
      bit++;
      mask<<=1;
    }
    if (sum==v) count++;
  }
  cout<<count<<endl;
  return 0;
}
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 01:08  [ТС]     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #6
Еще раз огромное спасибо. Пока ждал ответа вот сам накатал. Вроде правильно работает, исправь если что-то не так, буду признателен.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int v,vv,count=0;       //zlatopol 8.47
int g[10]={100,200,300,500,1000,1200,1400,1500,2000,3000};
cin>>v;
vv=v;
for (int j=9;j>=0;j--)
{
    vv=v;
    if (g[j]>vv) continue;
    vv-=g[j];
    if (vv==0) {count++; continue;}
for (int i=j-1;i>=0;i--)
{
    if (g[i]>vv) continue;
    vv-=g[i];
    if (vv==0) {count++; if (g[i]>200) vv=g[i];}
for (int k=i-1;k>=0;k--)
{
    if (g[k]>vv) continue;
    vv-=g[k];
    if (vv==0) {count++; if (g[i]>200) vv=g[k];}
}
}
}
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
19.01.2013, 01:20     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #7
Без 100 грамм не разобрать
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 01:32  [ТС]     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #8
Ну да. Рано я обрадовался... Что означает 0x3FF в условии for?

Добавлено через 5 минут
И что такое mask<<=1 ?
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
19.01.2013, 01:51     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Всё просто:
я делаю полный перебор всех состояний, которые могут попасть на весы (ну разве что кроме нулевого).
состояние кодируется двоичным числом.
Например
№бита 109876543210
число:...10011001010
Это значит, что на весах стоят 1я,3я,6я,7я,10я гири (те, номеру которых соответствует бит 1).
Мне нужно получить коды для всех возможных состояний весов.
Эти коды я получаю полным перебором двоичных чисел от 0000000001 до 1111111111
число 1111111111 это 0x3FF в шестнадцатиричной системе.
и действительно: счёт двоичными числами даёт все возможные состояния весов.
Например если б было 3 гири {100г 200г 300г}, я бы считал так
001 100
010 200
011 100+200
100 300
101 100+300
110 200+300
111 100+200+300
или
for (i=1; i<=7; i++){...}
Итого есть 7 способов поставить на весы 3 разные гири
Здесь код хранится в переменной i
чтобы сказать, какой этому коду соответствует вес, нужно пройтись в цикле по битам числа i и сложить в переменную sum те элементы массива, номера которых равны номерам единичных бит нашего кода это и делают строки 8-13

Добавлено через 1 минуту
Цитата Сообщение от Dezik Посмотреть сообщение
И что такое mask<<=1 ?
это сдвиг числа mask на 1 влево.
mask - это маска, которая накладывается на бит номер bit в коде, для проверки, равен ли он единице
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 02:05  [ТС]     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #10
Обалдеть.... Буду завтра препода просить растолковать мне всё это.... Спасибо!
Valli1
4 / 4 / 0
Регистрация: 14.09.2012
Сообщений: 64
21.01.2013, 02:41     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #11
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Ну так и задача не совсем для чайников.
Тогда такой способ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N=10;
int g[10]={100,200,300,500,1000,1200,1400,1500,2000,3000};
int main(){
  int mask, sum, bit, count=0;
  int v;
  cin>>v; 
  for (int i=1; i<=0x3FF;i++){
    mask=1, sum=bit=0;
    while(mask<=i){
      if(i&mask) sum+=g[bit];
      bit++;
      mask<<=1;
    }
    if (sum==v) count++;
  }
  cout<<count<<endl;
  return 0;
}
Поясните пожалуйста как у вас внутри цикла for формируется двоичное число. Как mask принимает значение 0?
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
21.01.2013, 02:55     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #12
а зачем "формировать двоичное число"?? Все числа и так двоичные.
Valli1
4 / 4 / 0
Регистрация: 14.09.2012
Сообщений: 64
21.01.2013, 03:43     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #13
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
а зачем "формировать двоичное число"?? Все числа и так двоичные.
Нет вы не поняли. Я хотел сказать, что насколько я понимаю из массива из 10 ти чисел 100... вы создаете множество множеств в виде 2чных чисел, напр. 100: 0000000001 и т.д. в данном случае в1й if пролазит только 100, правильно? И в сумму поступает 100. Как вы все остальное забиваете нулями?

Добавлено через 35 минут
Даже точнее тут не понятно: как добавляется 2, 3 и пр. 1цы. Ладно если одну единицу прогнать по всем 10ти значениям, как там образуется 2я и пр. 1цы. Напр:0000000011, что равно:100+200.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.01.2013, 04:03     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм
Еще ссылки по теме:
Сколькими способами можно разменять 100 000 рублей на монеты 1, 2, 5 рублей? C++
Сколькими способами из колоды (36 карт) можно выбрать неупорядоченный набор из 6 карт, удовлетворяющих условию C++
C++ Сколькими способами можно отобрать команду в составе 5 человек из 8 кандидатов;из 10 кандидатов; из 11 кандидатов? Подсчет количества способов отбора
Сколькими наборами из чисел X,Y,Z можно составить сумму S C++
Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы C++

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

Или воспользуйтесь поиском по форуму:
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
21.01.2013, 04:03     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм #14
я не понял, зачем ты мне ВЫкаешь.
ещё я не понял, что ты хотел мне сказать,
но догадываюсь, что ты ошибочно решил, что тут переводятся числа в разные системы счисления
Нет! перебираются все числа
от 1 до
1111111111 в двоичной
он же 0x3FF в 16ричной
он же 0177 в 8ричной
он же 1023 в 10ричной
В память будет занесено одно и то же число!
в С++ эти 3 операции ниже эквивалентны
C++
1
2
3
i=0x3FF;
i=0177;
i=1023;
информация всегда сохраняется в двоичном виде. в данном случае заполняются 4 байта памяти числом типа int
Yandex
Объявления
21.01.2013, 04:03     Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм
Ответ Создать тему
Опции темы

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