Сколькими способами гирями заданного набора весов можно составить вес в v грамм?

@Blimbablux · Регистрация: 14.09.2015

Author24 — интернет-сервис помощи студентам

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

@ПерС · 30.10.2015, 11:11

Достали диофантовыми уравнениями.
Ну, многими способами. Например, для 3 кг 599 способами, а для 9 тебе лучше и не знать

C

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
int main () {
 const int n = 10;
 int *a = (int *)malloc(n*sizeof(int)); //коэффиценты
 a[0]=100;
 a[1]=200;
 a[2]=300;
 a[3]=500;
 a[4]=1000;
 a[5]=1200;
 a[6]=1400;
 a[7]=1500;
 a[8]=2000;
 a[9]=3000;
 int k = 3000; //правая часть
 int *b = (int *)malloc(n*sizeof(int));
 int *c = (int *)malloc(n*sizeof(int));
 int i,j;
 for (i=0; i<n; i++) { b[i]=k/a[i]; c[i]=0; }
 long int s;
 int count=0;
 int found=0;
 do { //Начало цикла перебора
  s=0;
  for (i=0; i<n; i++) s+=a[i]*c[i];
  if (s==k) { //Вывод очередного решения c[i]
   printf ("\n%d) ",++count);
   for (i=0; i<n; i++) {
    printf ("%d*%d",a[i],c[i]);
    if (i<n-1) printf ("+");
   }
   printf ("=%d",k);
  }
  found = 0;
  for (i=n-1; i>-1; i--) {
   if (c[i]==b[i]) for (j=i; j<n; j++) c[j]=0;
   else { c[i]++; break; }
  }
  if (i<0) found = 1;
} while (!found); //Конец цикла перебора
 
fflush(stdin); getchar(); return 0;
}

@Blimbablux · 12.11.2015, 17:50 **[ТС]**

Не поможете с корректировкой) Задачу решил, но попросили переписать вот эти циклы одним (это часть кода)

C

#include "foo.h"
void foo(v) {
    int q, w, e, r, t, y, u, i, o, p, z;
    z=0;
    for (q=0; q<2; q++) {
            for (w=0; w<2; w++) {
                for (e=0; e<2; e++) {
                    for (r=0; r<2; r++) {
                        for (t=0; t<2; t++) {
                            for (y=0; y<2; y++) {
                                for (u=0; u<2; u++) {
                                    for (i=0; i<2; i++) {
                                        for (o=0; o<2; o++) {
                                            for (p=0; p<2; p++) {
                                                if (v==q*100+w*200+e*300+r*500+t*1000+y*1200+u*1400+i*1500+o*2000+p*3000) {
                                                    z++;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    printf("%d sposobov", z);
}

@ya_sergey_ · 10.11.2016, 15:57

я решил эту задачу на паскале. Проверьте, вроде работает
// Имеются 10 гирь весом 100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000 и 3000.
//Сколькими способами можно составить вес u граммов (u кратно 100).
var a:array [1..10] of word=(100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000, 3000);
i:byte;
k,s,x,x1,u:integer;

begin
readln(u);
k:=0;
for x:=1 to 1023 do
begin
x1:=x;
s:=0;
for i:=1 to 10 do
begin
s:=s+a[i]*(x1 mod 2);
x1:=x1 div 2;
end;
if s=u then k:=k+1;
end;
writeln(k);
end.

@Blimbablux 0 / 0 / 0 Регистрация: 14.09.2015 Сообщений: 54
		1
	Сколькими способами гирями заданного набора весов можно составить вес в v грамм? 30.10.2015, 10:17. Показов 6179. Ответов 3 Метки нет (Все метки) Имеются 10 гирь весом 100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000, 3000 г. Сколькими способами гирями этого набора можно составить вес в v грамм. 0

@ya_sergey_ 0 / 0 / 0 Регистрация: 10.11.2016 Сообщений: 1
	10.11.2016, 15:57	4
	я решил эту задачу на паскале. Проверьте, вроде работает // Имеются 10 гирь весом 100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000 и 3000. //Сколькими способами можно составить вес u граммов (u кратно 100). var a:array [1..10] of word=(100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000, 3000); i:byte; k,s,x,x1,u:integer; begin readln(u); k:=0; for x:=1 to 1023 do begin x1:=x; s:=0; for i:=1 to 10 do begin s:=s+a[i]*(x1 mod 2); x1:=x1 div 2; end; if s=u then k:=k+1; end; writeln(k); end. 0