#include <time.h>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
int main( ) {
int * a, * b;
int i, m, n;
printf ( "Введите n - длину прямой, m - длину отрезка\n " ) ; int k = n; //Какое лучше взять??? Это количество отрезков
a
= ( int * ) malloc ( k
* sizeof ( int ) ) ; b
= ( int * ) malloc ( k
* sizeof ( int ) ) ; //Perehod_esli_ne_pokrivaet
int usl = 0 ;
while ( usl = 0 ) {
usl = 1 ;
for ( i = 0 ; i < k; i++ ) {
a
[ i
] = - n
+ rand ( ) % ( 2 * n
) ; b
[ i
] = a
[ i
] + rand ( ) % ( n
- a
[ i
] ) ; if ( a[ i] = b[ i] ) {
i--;
}
}
//проверка на покрытие отрезка
int j;
for ( i = - m; i < m+ 1 ; ) {
j = 0 ;
while ( ( j != - 1 ) && ( j < k) ) {
if ( ( i < b[ j] + 1 ) && ( i > a[ j] - 1 ) ) {
i = b[ j] + 1 ;
z = - 1 ;
}
else {
j++;
}
}
if ( j > k- 1 ) {
//goto Perehod_esli_ne_pokrivaet //Выход из цикла. Сгенерировать последовательность отрезков заново
usl = 0 ;
}
}
}
//Создание минимального покрытия
int * c;
c
= ( int * ) malloc ( k
* sizeof ( int ) ) ; for ( i = 0 ; i < k; i++ ) {
c[ i] = 0 ;
}
int max, Nmax, j;
i = - m;
int nomotr = 1 ;
while ( i < m+ 1 ) {
max = - 1 ;
Nmax = - 1 ;
for ( j = 0 ; j < k; j++ ) {
if ( ( i < b[ j] + 1 ) && ( i > a[ j] - 1 ) ) {
if ( b[ j] - i > max) {
Nmax = j;
}
}
}
c[ Nmax] = nomotr;
nomotr++;
i = b[ Nmax] + 1 ;
}
//Выводим отрезки
for ( i = 0 ; i < nomotr; i++ ) {
j = 0 ;
while ( c[ j] != i- 1 ) {
j++;
}
printf ( "Отрезок %d: [%d; %d]\n " , i
, a
[ j
] , b
[ j
] ) ; }
//free(a);
return 0 ;
}
I2luY2x1ZGUgPHRpbWUuaD4KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxtYWxsb2MuaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgppbnQgbWFpbigpIHsKCWludCAqYSwgKmI7CglpbnQgaSwgbSwgbjsKCXNyYW5kKHRpbWUoTlVMTCkpOwoJcHJpbnRmKCLQktCy0LXQtNC40YLQtSBuIC0g0LTQu9C40L3RgyDQv9GA0Y/QvNC+0LksIG0gLSDQtNC70LjQvdGDINC+0YLRgNC10LfQutCwXG4iKTsKCXNjYW5mKCIlZCVkIiwgJm4sICZtKTsKCWludCBrID0gbjsgLy/QmtCw0LrQvtC1INC70YPRh9GI0LUg0LLQt9GP0YLRjD8/PyDQrdGC0L4g0LrQvtC70LjRh9C10YHRgtCy0L4g0L7RgtGA0LXQt9C60L7QsgoJYSA9IChpbnQqKSBtYWxsb2MoaypzaXplb2YoaW50KSk7CgliID0gKGludCopIG1hbGxvYyhrKnNpemVvZihpbnQpKTsKCS8vUGVyZWhvZF9lc2xpX25lX3Bva3JpdmFldAoJaW50IHVzbCA9IDA7Cgl3aGlsZSAodXNsID0gMCl7CgkJdXNsID0gMTsKCQlmb3IgKGkgPSAwOyBpIDwgazsgaSsrKXsKCQkJYVtpXSA9IC1uK3JhbmQoKSAlICgyKm4pOwoJCQliW2ldID0gYVtpXSArIHJhbmQoKSAlIChuLWFbaV0pOwoJCQlpZiAoYVtpXSA9IGJbaV0pewoJCQkJaS0tOwoJCQl9CgkJfQoJCS8v0L/RgNC+0LLQtdGA0LrQsCDQvdCwINC/0L7QutGA0YvRgtC40LUg0L7RgtGA0LXQt9C60LAKCQlpbnQgajsKCQlmb3IgKGkgPSAtbTsgaSA8IG0rMTsgKXsKCQkJaiA9IDA7CgkJCXdoaWxlICgoaiAhPSAtMSkmJihqIDwgaykpewoJCQkJaWYgKChpIDwgYltqXSsxKSYmKGkgPiBhW2pdLTEpKXsKCQkJCQlpID0gYltqXSsxOwoJCQkJCXogPSAtMTsKCQkJCX0KCQkJCWVsc2V7CgkJCQkJaisrOwoJCQkJfQoJCQl9CgkJCWlmIChqID4gay0xKXsKCQkJCS8vZ290byBQZXJlaG9kX2VzbGlfbmVfcG9rcml2YWV0IC8v0JLRi9GF0L7QtCDQuNC3INGG0LjQutC70LAuINCh0LPQtdC90LXRgNC40YDQvtCy0LDRgtGMINC/0L7RgdC70LXQtNC+0LLQsNGC0LXQu9GM0L3QvtGB0YLRjCDQvtGC0YDQtdC30LrQvtCyINC30LDQvdC+0LLQvgoJCQkJdXNsID0gMDsKCQkJfQoJCX0KCX0KCS8v0KHQvtC30LTQsNC90LjQtSDQvNC40L3QuNC80LDQu9GM0L3QvtCz0L4g0L/QvtC60YDRi9GC0LjRjwoJaW50ICpjOwoJYyA9IChpbnQqKSBtYWxsb2MoaypzaXplb2YoaW50KSk7Cglmb3IgKGkgPSAwOyBpIDwgazsgaSsrICl7CgkJY1tpXSA9IDA7Cgl9CglpbnQgbWF4LCBObWF4LCBqOwoJaSA9IC1tOwoJaW50IG5vbW90ciA9IDE7Cgl3aGlsZSAoaSA8IG0rMSl7CgkJbWF4ID0gLTE7CgkJTm1heCA9IC0xOwoJCWZvciAoaiA9IDA7IGogPCBrOyBqKyspewoJCQlpZiAoKGkgPCBiW2pdKzEpJiYoaSA+IGFbal0tMSkpewoJCQkJaWYgKGJbal0taSA+IG1heCl7CgkJCQkJTm1heCA9IGo7CgkJCQl9CgkJCX0gCgkJfQoJCWNbTm1heF09bm9tb3RyOwoJCW5vbW90cisrOwoJCWkgPSBiW05tYXhdKzE7Cgl9CgkvL9CS0YvQstC+0LTQuNC8INC+0YLRgNC10LfQutC4Cglmb3IgKGkgPSAwOyBpIDwgbm9tb3RyOyBpKyspewoJCWogPSAwOwoJCXdoaWxlKGNbal0gIT0gaS0xKXsKCQkJaisrOwoJCX0KCQlwcmludGYoItCe0YLRgNC10LfQvtC6ICVkOiBbJWQ7ICVkXVxuICIsIGksIGFbal0sIGJbal0pOwoJfQoJLy9mcmVlKGEpOwoJcmV0dXJuIDA7Cn0=