1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| /*Необходимо разработать программу согласно варианту задания.
При написании программы реализовать рекурсивную функцию.
Работу рекурсивной функции продемонстрировать в функции main.
Программу реализовать в диалоговом режиме: запрос данных - вывод ответа.
После каждого вывода ответа запрашивать у пользователя выход и,
в случае положительного ответа, осуществлять завершение программы.
------------------------------------------------------------------
Дан список предметов, характеризующихся длиной и шириной.
Расставить предметы так, чтобы прямоугольный контур,
обведенный вокруг предметов, был наименьшей площади.
Предметы можно поворачивать. Ставить один предмет на другой предмет нельзя. (40 баллов).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <time.h>
#include <math.h>
typedef struct { int len, width; }TYPE;
typedef enum { FALSE, TRUE }Bool;
void vvod( TYPE (*), int);
char *circuit( TYPE (*), int , char [] ); // первоначальный контур
void extr( TYPE (*), int, int, int); // основная функция ( возвращает формат (AxB), где A и B длина и ширина
void FreeList ( TYPE(**) );
int main( int argc, char *argv[ ] )
{
srand( time( NULL ) );
int n; // кол - во предметов
printf( "Enter count of objects: n \nEnter: " );
int d = scanf( "%d", &n);
while( d < 1 || n <= 0 ) // проверка ввода
{
while( getchar( ) != '\n');
printf( "Repeat: " ); d = scanf( "%d", &n);
}
TYPE *list = ( TYPE*)malloc(sizeof(TYPE)*n); // выделение памяти под списки предметов
vvod( list, n );
int i;
for( i = 0; i < n; i++ ) printf("Object %1i: %ix%i\n", i+1, list[i].len, list[i].width );
/*выбор оптимального материала для всех объектов*/
char ar[10], *ptr = NULL;
ptr = circuit( list, n, ar );
printf( "First circuit has square: %s\n", ptr );
int a, b;
char c;// ненужная переменная для корректной работы функции sscanf
sscanf( ptr, "%i%c%i", &a, &c, &b );// a, b - длина и ширина первого неоптимального контура
/*-------*/
extr( list, n, a, b );
/*-------*/
FreeList( &list );
system( "pause" );
getch( );
return 0;
}
void vvod( TYPE *list, int size )
{
int i;
if( !list ) { printf( "Memory error."); return; }
else
{
for( i = 0; i < size; i++ )
{
list[i].len = rand( )%6 + 1;
list[i].width = rand( )%5 + 1;
}
}
}
void swap( int *a1, int *b1 ) // функция замены длины и ширины местами
{
int temp = *a1;
*a1 = *b1;
*b1 = temp;
}
char *circuit( TYPE *list, int size, char cirsize[] )// вспомогательная функция поиска начального контура
{
int i;
int a = 0, max = 0;
for( i = 0; i < size; i++ ) a += list[i].len;
for( i = 0; i < size; i++ ) if( list[i].width > max ) max = list[i].width;
char mass1[20], mass2[6];
itoa( a, mass1, 10 );
itoa( max, mass2, 10 );
strcat( mass1, "x");
strcat( mass1, mass2 );
strcpy( cirsize, mass1 );
return cirsize;
}
void extr( TYPE *list, int size, int len, int width ) // рекурсивная функция поиска оптимального контура
{
int i, j;
// отыскание оптимальной длины
int sumlen;
for( i = 0; i < size; i++ )
{
sumlen = list[i].width;
for( j = 0; j < size; j++ ) if( j != i ) sumlen += list[j].len;
// printf("%d\n",sumlen );
if( sumlen < len && list[i].len <= width )
{
swap( &list[i].len, &list[i].width );
printf( "%dx%d\n", sumlen, width);
return extr( list, size, sumlen, width);
}
}
// отыскания оптимальной ширины
int maxwidth = width;
}
void FreeList ( TYPE **list )
{
free( *list );
*list = NULL;
} |
(
