матрицы и деревья(чистый С)

[patriarch]

нужна помощь с двумя задачами.Помогите пожалуйста.
1) Игры.
Заполнить матрицу размера 5 на 5 цифрами (не числами) таким образом, чтобы цифры
в строках и столбцах не повторялись, совпадали суммы цифр по столбцам и по
строкам, а также были бы простыми все пятизначные числа, изображенные строками и
столбцами матрицы
2)Геометрия.
Задано n точек на плоскости. Построить дерево с вершинами в данных точках так,
чтобы была минимальной суммарная длина его рёбер.

[Sasha_Smirnov]

1) попробовал прикинуть упрощённый (!) вариант: с одним повтором. А иначе-то как?! Только 4 на 4.

1 3 3 7 9
3 1 7 9 3
3 7 9 3 1
7 9 3 1 3
9 3 1 3 7

Осталось проверить полученные 5-значные числа на простоту...

А на самом деле вы (или до вас?!) что-то перепутали: простые числа (кроме числа 2) оканчиваются на 1, 3, 7 или 9. Получается, что (в тех условиях, что у вас) мы даже не можем заполнить (разными цифрами!) все 5 клеток, ибо допустимых цифр всего 4.

3 9 9 7 1
1 3 7 9 9
7 1 9 9 3
9 7 3 1 9
9 9 1 3 7

Вот, с повтором 9-ки почти получилось! Осталось только 3 числа (они выделены) не простых: 97319 = 307·317; 79913 = 157·509 и 19397 = 7·2771. Как видите, даже упрощённая задача не факт что решается. Без программы не найти! В приемлемые сроки.



2) может быть, не дерево (оно м. б. двоичным, 3-ичным... (n–1)-ичным...), а граф?!

[patriarch]

Да вы правы сегодня разговаривал с преподователем.В задаче на матрицу условие простоты лишнее.А вот насчет дерева,в задачах которые нам выдали сказано дерево и преподователь тоже говорит дерево,но думаю что можно считать и граф,суть не слишком измениться...

[Sasha_Smirnov]

Ну тогда, условно говоря, это будет не дерево (ветвистое), а куст.

Что-то мало энтузиазма... Задачи-то классные. (А сам я на Си не пишу.)

[Sazary]

Раз простота чисел отпадает, то вот первая.
Притом выдает разные комбинации.

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

int check(int **M, int numi, int numj, int value)
{
int i;
for(i=numi-1;i>=0;i--)
 if(M[i][numj]==value)
  return 0;
for(i=numj-1;i>=0;i--)
 if(M[numi][i]==value)
  return 0;
return 1;
}
//------------


int main()
{
const int N = 5;
int i,j,k,l,**matr,*mas,nm=0;
int b=0,cnt=0;
srand(time(NULL));

matr = (int**)malloc(N*sizeof(int*));
for(i=0;i<N;i++)
 matr[i] = (int*)malloc(N*sizeof(int));

mas = (int*)malloc(N*sizeof(int));

//=========================
for(i=0;i<N;i++)
 {
  nm = 0;
  cnt = 0;
  for(j=0;j<N;j++)
   {
    b=0;
    while(b==0)
     {
      k = rand()%N+1;
      b = 1;
      for(l=0;l<nm;l++)
       if(k==mas[l])
        b = 0;

     } // while

    if(check(matr,i,j,k)==1)
     {
      matr[i][j] = k;
      mas[nm++] = k;
     }
    else j--;
    cnt++;
    if(cnt>=100)
     {
      i--;
      break;
     }
   } // for j


 } //for i
//---------------------------

for(i=0;i<N;i++)
 {
  for(j=0;j<N;j++)
    printf("%4d",matr[i][j]);
  printf("\n");
 }


free(mas);
for(i=0;i<N;i++)
 free(matr[i]);
free(matr);

getch();
return 0;
}

Массивы сделал динамическими, потому что мне так удобнее )
Переменную b можно (даже лучше) сделать типа bool, но я сделал int для совместимости со старыми компиляторами.

upd Прикрепил исходник с экзешником.

[patriarch]

Sazary спасибо огромное!но зачем закоментированные строки и мы изучаем С всего месяц и не изучали ни динамические массивы ни библиотеку <time.h> зачем она тут вообще?

[Sazary]

зачем закоментированные строки

Для лучшей читабельности.

<time.h> зачем она тут вообще?

Для инициализации генератора случайных чисел.

srand(time(NULL));

мы изучаем С всего месяц и не изучали ни динамические массивы

Ну вот вам со статичными:

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

int check(int *M, int n, int numi, int numj, int value)
{
int i;
for(i=numi-1;i>=0;i--)
 if(M[i*n + numj]==value)
  return 0;
for(i=numj-1;i>=0;i--)
 if(M[numi*n + i]==value)
  return 0;
return 1;
}
//------------


int main()
{
const int N = 5;
int i,j,k,l,matr[N][N],mas[N],nm=0;
int b=0,cnt=0;
srand(time(NULL));

//=========================
for(i=0;i<N;i++)
 {
  nm = 0;
  cnt = 0;
  for(j=0;j<N;j++)
   {
    b=0;
    while(b==0)
     {
      k = rand()%N+1;
      b = 1;
      for(l=0;l<nm;l++)
       if(k==mas[l])
        b = 0;

     } // while

    if(check(&matr[0][0],N,i,j,k)==1)
     {
      matr[i][j] = k;
      mas[nm++] = k;
     }
    else j--;
    cnt++;
    if(cnt>=100)
     {
      i--;
      break;
     }
   } // for j


 } //for i
//---------------------------

for(i=0;i<N;i++)
 {
  for(j=0;j<N;j++)
    printf("%4d",matr[i][j]);
  printf("\n");
 }

getch();
return 0;
}

[patriarch]

Для лучшей читабельности.

то есть их впринципе можно удалить?

Для инициализации генератора случайных чисел.

Это только для того чтобы выдавал разные комбинации?

[Sazary]

то есть их впринципе можно удалить?

Да.

Это только для того чтобы выдавал разные комбинации?

Да. Но я бы вам советовал просто почитать про эту функцию, вместо того, чтобы удалять.

[patriarch]

Извините за наглость,а со второй никто не поможет?