Перебор всех возможных вариантов

[[MI_nor]]

Вопрос: как перебрать в матрице все возможные значения? Т.е например
имея матрицу размерностью 4, постепенно получать матрицу от
0 0 0 0, до 999 999 999 999.

[wyvern]

int matr[M][N];
// заполняем
for(int i=0;i<M;i++)
    for(int j=0;j<N;j++)
       print("%d", matr[i][j]); // ну или чего там

Или Вы что-то другое имели ввиду? Если да, поподробнее...

[[MI_nor]]

эээ, ну да) сорри не тупо матрица, а матрица строка...массив одномерный =)
к примеру имея массив х[n] нужно подставлять его в опр уравнение, постепенно меняя значения его элементов. т.е к примеру в первый проход массив был равен 0 0 0 0, во второй 0 0 0 1, в третий 0 0 1 0, а 55й 3 12 3 1 =) и так до опр условия)

[Sazary]

[MI_nor], ну, все-таки одномерный массив - это не матрица..
Код ниже дает такие массивы:
0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 3
.........
0 3 34 3
0 3 34 4
....
и т.д

uses crt;

const N=4;
max = 999;
var
a : array[1..N] of integer;
i,j : integer;

begin
clrscr;

while a[1]<=max do
 begin
 for i:=1 to N do
  write(a[i]:4);
 writeln;

 inc(a[N]);
 for i:=N downto 1 do
  begin
  if a[i]>max then
   begin
   inc(a[i-1]);
   a[i] := 0;
   end;
  end;

 if keypressed then
  if readkey = #27 then break;
 end;

readln;
end.

Считать

от 0 0 0 0, до 999 999 999 999.

на моем компьютере (не слабом) будет, если я правильно посчитал, 415417.92 часов, или 47.4 лет. (это с выводом всех комбинаций)

[[MI_nor]]

Хорошо, попробуем по другому.
Условие задачи: Даны натуральные числа н масив а1...ан. б - число способов выплатить сумму к, т.е это число решекний уравнения а1х1+а2х2+...+анхн=к, где х может принимать любые нелые неотрицательные значения. определить число способов выплаты заданной суммы.
Собсна код:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

int a[50],x[50];
int k,n,kol=0;

void cleararray(int mas[50], int N)
 {
  for(int i=0;i<N;i++)
   {
    mas[i]=0;
   }
 }

void xmasaddone()
 {
  randomize();
  int buf;
  buf=random(n);
  x[buf]++;
 }

void proverka()
 {
  while (x[0]<90)
   {
    int sum=0;
    for (int i=0;i<n;i++)
     {
      sum+=a[i]*x[i];
     }
    if (k==sum) {kol++;  for (int i=0;i<n;i++)
			  {
			   printf("%d ",x[i]);
			  }
			 printf("\n");
		}
    xmasaddone();
    proverka();
   }
 }

void main()
 {
  clrscr();
  printf("Vvedite kol-vo elementov uravneniya - ");
  scanf("%d",&n);
  clrscr();
  printf("Vvedite:\n");
  for(int i=0;i<n;i++)
   {
    printf("a[%d]",i+1);
    scanf("%d",&a[i]);
   }
  cleararray(x,n);
  clrscr();
  printf("Vvedite summu k - ");
  scanf("%d",&k);
  proverka();
  printf("\n%d",kol);
  getch();
 }

х[0]<90 - случайное условие, потом подумаю до какого момента тут нужно изменять массив, а функция xmasaddone должна изменять массив х, чтобы проверять всевозможные способы подстановки в уравнения и считать.

[Sazary]

Не понял, зачем вам там random нужен..
В общем, переписал через рекурсию. Вроде, все правильно.

#include <stdio.h>
#include <conio.h>

int a[100],cnt=0,N,K;

void fun(long S, int tek)
{
 if(tek==N)
  {
   if(S==K) cnt++;
   return;
  }
 if(S>K) return;
//--
for(int i=0; S+a[tek]*i<=K; i++)
 {
  fun(S+a[tek]*i, tek+1);
 }
}
//--------------

int main()
{
int i;

printf("Vvedite N: ");
scanf("%d",&N);
for(i=0;i<N;i++)
 {
  printf("Vvedite a[%d]: ",i);
  scanf("%d",&a[i]);
 }
printf("\nVvedite K: ");
scanf("%d",&K);
printf("\n------------------\n");
fun(0,1);
printf("Kolichestvo variantov = %d\n",cnt);

getch();
return 0;
}

[[MI_nor]]

Sazary, "S+a[tek]*i<=K" что значит это условие? просто если ввести 2 элемента 5 и 10, а сумму 100, то там масса вариантов, но программа предлагает всего 2

[Sazary]

[MI_nor], да, действительно.. Как-то не особо проверял.
Сейчас подумаю.

S+a[tek]*i<=K

S - текущая сумма (та, что уже успела накопиться).
a[tek] - элемент массива

-------------
Вот такую попробуйте.

#include <stdio.h>
#include <conio.h>

int a[100],cnt=0,N,K;

void fun(long S, int tek)
{
 if(tek==N)
  {
   if(S==K) cnt++;
   return;
  }

 for(int i=0; S+a[tek]*i<=K; i++)
  fun(S+a[tek]*i, tek+1);

}
//--------------

int main()
{
int i;

printf("Vvedite N: ");
scanf("%d",&N);
for(i=0;i<N;i++)
 {
  printf("Vvedite a[%d]: ",i);
  scanf("%d",&a[i]);
 }
printf("\nVvedite K: ");
scanf("%d",&K);
printf("\n------------------\n");
fun(0,0);
printf("Kolichestvo variantov = %d\n",cnt);

getch();
return 0;
}

Вообще, хорошо бы если б вы дали какой-нибудь контрольный вариант, чтобы можно было проверить.

[Sazary]

Добавил вывод всех вариантов. Вроде, все верно.

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>

int a[100],cnt=0,N,K;

void fun(long S, int tek, char str[])
{
 char tmp[500],buf[20];
 if(tek==N)
  {
   if(S==K)
    {
     cnt++;
     printf("%s\n",str);
    }
   return;
  }

 for(int i=0; S+a[tek]*i<=K; i++)
  {
   itoa(a[tek],buf,10);
   strcpy(tmp,str);
   if(strcmp(tmp,"")!=0) strcat(tmp," + ");
   strcat(tmp,buf);
   itoa(i,buf,10);
   strcat(tmp,"*");
   strcat(tmp,buf);
   fun(S+a[tek]*i, tek+1,tmp);
  }

}
//--------------

int main()
{
int i;
char str[500];

printf("Vvedite N: ");
scanf("%d",&N);
for(i=0;i<N;i++)
 {
  printf("Vvedite a[%d]: ",i);
  scanf("%d",&a[i]);
 }
printf("\nVvedite K: ");
scanf("%d",&K);
printf("\n------------------\n");
strcpy(str,"");
fun(0,0,str);
printf("Kolichestvo variantov = %d\n",cnt);

getch();
return 0;
}

[[MI_nor]]

Да, действительно, все работает, спасибо. Ушел понимать рекурсию=)