Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/25: Рейтинг темы: голосов - 25, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
1

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

17.01.2013, 13:05. Показов 4652. Ответов 16
Метки нет (Все метки)

Имееться 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.01.2013, 13:05
Ответы с готовыми решениями:

Сколькими способами гирями этого набора можно составить вес в V грамм
Имеются 10 гирь весом 100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000 и 3000 г. Сколькими...

Сколькими способами гирями заданного набора можно составить вес в v грамм
Имеются 10 гирь весом 100, 200, 300, 500, 1000, 1200, 1400, 1400, 1500, 2000 и 2000г. Сколькими ...

Сколькими способами гирями заданного набора весов можно составить вес в v грамм?
Имеются 10 гирь весом 100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000, 3000 г. Сколькими способами...

Сколькими способами можно при помощи гирь набрать вес в v грамм
Доброго времени суток. У меня есть задача со следующим условием: . Я написал такой код на C++ и...

16
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
3409 / 2768 / 751
Регистрация: 25.03.2012
Сообщений: 10,042
Записей в блоге: 1
18.01.2013, 23:24 3
гугли динамическое программирование.
1
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 00:19  [ТС] 4
Да рано вроде еще. Только начали учить си. Но все равно спасибо за совет!
0
3409 / 2768 / 751
Регистрация: 25.03.2012
Сообщений: 10,042
Записей в блоге: 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;
}
3
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
3409 / 2768 / 751
Регистрация: 25.03.2012
Сообщений: 10,042
Записей в блоге: 1
19.01.2013, 01:20 7
Без 100 грамм не разобрать
1
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 01:32  [ТС] 8
Ну да. Рано я обрадовался... Что означает 0x3FF в условии for?

Добавлено через 5 минут
И что такое mask<<=1 ?
0
3409 / 2768 / 751
Регистрация: 25.03.2012
Сообщений: 10,042
Записей в блоге: 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
0 / 0 / 0
Регистрация: 17.01.2013
Сообщений: 7
19.01.2013, 02:05  [ТС] 10
Обалдеть.... Буду завтра препода просить растолковать мне всё это.... Спасибо!
0
4 / 4 / 4
Регистрация: 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
3409 / 2768 / 751
Регистрация: 25.03.2012
Сообщений: 10,042
Записей в блоге: 1
21.01.2013, 02:55 12
а зачем "формировать двоичное число"?? Все числа и так двоичные.
0
4 / 4 / 4
Регистрация: 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
3409 / 2768 / 751
Регистрация: 25.03.2012
Сообщений: 10,042
Записей в блоге: 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
0 / 0 / 0
Регистрация: 23.10.2016
Сообщений: 6
26.08.2019, 19:20 15
можете пожайлуста сделать блоксхему к етому коду. Буду очень благодарна)
0
812 / 500 / 210
Регистрация: 19.01.2019
Сообщений: 1,196
27.08.2019, 01:16 16
Немного рекурсии?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
size_t fun(uint32_t num, size_t ind = 0, uint32_t res = 0) {
    static int arr[] = { 100,200,300,500,1000,1200,1400,1500,2000,3000 };
    if (ind == sizeof(arr) / sizeof(*arr)) {
        return res == num ? 1 : 0;
    }
    return fun(num, ind + 1, res) + fun(num, ind + 1, res + arr[ind]);
}
 
int main()
{
    uint32_t num;
    std::cin >> num;
    std::cout << fun(num) << '\n';
 
    return 0;
}
0
3409 / 2768 / 751
Регистрация: 25.03.2012
Сообщений: 10,042
Записей в блоге: 1
29.08.2019, 21:00 17
olyahappy16, блок-схемы нафиг никому не сдались из профессиональных программистов
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.08.2019, 21:00

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Сколькими способами из 7 элементов можно выбрать два набора?
Сколькими способами из 7 элементов можно выбрать два набора так, чтобы их объединение состояло из...

Сколькими способами можно раскрасить стороны данного правильного n-угольника?
Имеется k красок. Сколькими способами можно раскрасить стороны данного правильного n-угольника так,...

Сколькими способами можно составить расписание
В третьем классе изучается 10 предметов. В понедельник 4 урока. Сколькими способами можно составить...

Сколькими способами можно составить букет?
4)есть 8 разных цветов. Сколькими способами из них можно составить букет, который содержит непарное...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Опции темы

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