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

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

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

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

17.01.2013, 13:05. Просмотров 1575. Ответов 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;
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.01.2013, 13:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм (C++):

Сколькими способами можно купить 185 кг ящиками по 15, 17 и 21 кг - C++
В магазине продается мастика в ящиках по 15 кг,17 кг,21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики?Сколькими способами можно...

Комбинаторика: сколькими способами можно отправить на олимпиаду 3 из 17 учеников? - C++
В классе есть 17 учеников. Нужно отправить на олимпиаду 3 учеников с класса, сколькими способами можно отправить учеников? Думаю 17^3? ...

Сколькими возможными способами можно рассадить на n стульев n человек? - C++
Нужна помощь. Есть код, но не уверен что сделал как надо. В комнате n стульев. Определить, сколькими возможными способами можно...

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

Требуется вычислить сколькими способами можно получить строку В из строки А - C++
заданы 2 символьные строки А и Б . Требуется вычислить сколькими способами можно получить строку В из строки А, вычеркивая некоторые...

Определить сколькими различными способами можно подняться на заданную ступеньку (Лестница в Небо) - C++
Определить сколькими различными способами можно подняться на десятую ступеньку, если за шаг можно подняться следующую или через одну. Как...

13
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
18.01.2013, 23:18  [ТС] #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;
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
18.01.2013, 23:24 #3
гугли динамическое программирование.
1
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 00:19  [ТС] #4
Да рано вроде еще. Только начали учить си. Но все равно спасибо за совет!
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
19.01.2013, 00:32 #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;
}
1
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 01:08  [ТС] #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];}
}
}
}
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
19.01.2013, 01:20 #7
Без 100 грамм не разобрать
0
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 01:32  [ТС] #8
Ну да. Рано я обрадовался... Что означает 0x3FF в условии for?

Добавлено через 5 минут
И что такое mask<<=1 ?
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
19.01.2013, 01:51 #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 в коде, для проверки, равен ли он единице
3
Dezik
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 02:05  [ТС] #10
Обалдеть.... Буду завтра препода просить растолковать мне всё это.... Спасибо!
0
Valli1
4 / 4 / 0
Регистрация: 14.09.2012
Сообщений: 64
21.01.2013, 02:41 #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?
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
21.01.2013, 02:55 #12
а зачем "формировать двоичное число"?? Все числа и так двоичные.
0
Valli1
4 / 4 / 0
Регистрация: 14.09.2012
Сообщений: 64
21.01.2013, 03:43 #13
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
а зачем "формировать двоичное число"?? Все числа и так двоичные.
Нет вы не поняли. Я хотел сказать, что насколько я понимаю из массива из 10 ти чисел 100... вы создаете множество множеств в виде 2чных чисел, напр. 100: 0000000001 и т.д. в данном случае в1й if пролазит только 100, правильно? И в сумму поступает 100. Как вы все остальное забиваете нулями?

Добавлено через 35 минут
Даже точнее тут не понятно: как добавляется 2, 3 и пр. 1цы. Ладно если одну единицу прогнать по всем 10ти значениям, как там образуется 2я и пр. 1цы. Напр:0000000011, что равно:100+200.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
21.01.2013, 04:03 #14
я не понял, зачем ты мне ВЫкаешь.
ещё я не понял, что ты хотел мне сказать,
но догадываюсь, что ты ошибочно решил, что тут переводятся числа в разные системы счисления
Нет! перебираются все числа
от 1 до
1111111111 в двоичной
он же 0x3FF в 16ричной
он же 0177 в 8ричной
он же 1023 в 10ричной
В память будет занесено одно и то же число!
в С++ эти 3 операции ниже эквивалентны
C++
1
2
3
i=0x3FF;
i=0177;
i=1023;
информация всегда сохраняется в двоичном виде. в данном случае заполняются 4 байта памяти числом типа int
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.01.2013, 04:03
Привет! Вот еще темы с ответами:

Сколькими способами можно изменить заданную последовательность, чтобы она осталась возрастающей? - C++
Дана последовательность из N различных чисел. Сколькими способами можно удалить из нее ка- кие-то числа, чтобы оставшаяся...

Составить программу для сортировки данного набора строк по символу - C++
Составить программу для сортировки данного набора строк по символу с номером k&gt;0. Значение k не превосходит длины с самой короткой строки...

Сколькими способами можно разменять 100 000 рублей на монеты 1, 2, 5 рублей? - C++
Задача такова: сколькими способами можно разменять 100 000 рублей на монеты 1 2 5 рублей,то есть нужно выписать количество решений...

Сколькими способами из колоды (36 карт) можно выбрать неупорядоченный набор из 6 карт, удовлетворяющих условию - C++
Сколькими способами из колоды 36 карт можно выбрать неупорядоченный набор из 6 карт, чтобы в этом наборе было бы точно: 2 дамы, 1 туз, 2...


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

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

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