Примеры решения задач динамическим данным(динамике, динамическому программированию )
Пример 1
Список точек в двумерном пространстве вводится пользователем: сначала указывается количество элементов в списке, а затем вводятся сами элементы в формате (x,y). Определить две точки в списке максимально удаленные друг от друга и две точки – максимально приближенные друг к другу. Найденные точки вывести в формате: (x,y) – (x,y) : расстояние. Список точек создается в динамической памяти.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char *argv[])
{
typedef struct{double x,y;} Point2D;
int num;
printf("Введите количество точек: "); scanf("%d",&num);
if(num < 3) {puts("Слишком мало точек!"); return 0;}
Point2D *list = (Point2D *)calloc(num,sizeof(Point2D));
if(!list) {puts("Недостаточно памяти!"); return 0;}
puts("Введите список точек: ”);
for(int i=0;i<num;i++){
fflush(stdin);
scanf("(%lf,%lf)",&list[i].x,&list[i].y);
}
int mins[2] = {0,1}, maxs[2] = {0,1};
double min = sqrt(
pow(list[0].x-list[1].x,2.0)+
pow(list[0].y-list[1].y,2.0)
),
max = min;
for(int i=0;i<num-1;i++)
for(int j=i+1;j<num;j++){
double len = sqrt(
pow(list[i].x-list[j].x,2.0)+
pow(list[i].y-list[j].y,2.0)
);
if(len > max){
max = len; maxs[0] = i; maxs[1] = j;
}else if(len < min){
min = len; mins[0] = i; mins[1] = j;
}
}
printf("MAX: (%.2lf,%.2lf) - (%.2lf,%.2lf) : %.2lf\n",
list[maxs[0]].x,list[maxs[0]].y,
list[maxs[1]].x,list[maxs[1]].y,max);
printf("MIN: (%.2lf,%.2lf) - (%.2lf,%.2lf) : %.2lf\n",
list[mins[0]].x,list[mins[0]].y,
list[mins[1]].x,list[mins[1]].y,min);
free(list);
return 0;
}
Пример 2
Список окружностей (координаты центра и радиус) вводится пользователем: сначала вводится количество элементов в списке, а затем – сами элементы в формате (x,y) radius. Необходимо удалить из списка все окружности, длина которых меньше средней длины. Полученный список вывести на экран.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[])
{
typedef struct{double x,y,r;} CIRCLE;
int num;
printf("Введите количество записей: "); scanf("%d",&num);
if(num < 2) {puts("Слишком мало записей!"); return 0;}
CIRCLE *list = (CIRCLE *)calloc(num,sizeof(CIRCLE));
if(!list) {puts("Few memory!"); return 0;}
double midlen = 0;
puts("Введите список: ");
for(int i=0;i<num;i++){
fflush(stdin);
scanf("(%lf,%lf) %lf",
&list[i].x,&list[i].y,&list[i].r);
midlen += 2.0*list[i].r*pi;
}
midlen /= num;
for(int i=0;i<num;i++)
if(2.0*list[i].r*pi < midlen){
memcpy(&list[i],&list[i+1],sizeof(CIRCLE)*(num-i-1));
num--;
i--;
}
list = (CIRCLE *)realloc(list,num);
puts("Результат: ”);
for(int i=0;i<num;i++)
printf("(%.2lf,%.2lf) %.2lf\n",
list[i].x,list[i].y,list[i].r);
free(list);
return 0;
}
Пример 3
Создать в динамической памяти вещественную матрицу размера N×M (вводятся пользователем). Осуществить ввод матрицы. Упорядочить строки матрицы в порядке увеличения или уменьшения суммы их элементов (направление выбирает пользователь). Полученную матрицу вывести на экран.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[])
{
int n,m;
printf("Введите размеры матрицы: ");
scanf("%d %d",&n,&m);
if((n<2)||(m<2)) {puts("Неправильный ввод!"); return 0;}
double **matrix = (double **)calloc(n,sizeof(double *));
if(!matrix) {puts("Мало памяти!"); return 0;}
double *summs = (double *)calloc(n,sizeof(double));
if(!summs) {
free(matrix);
puts("Мало памяти!"); return 0;
}
for(int i=0;i<n;i++){
summs[i] = 0.0;
matrix[i] = (double*)calloc(m,sizeof(double));
if(!matrix[i]){
for(int j=0;j<i;j++) free(matrix[i]);
free(matrix); free(summs);
puts("Мало памяти!"); return 0;
}
}
puts("Введите матрицу:");
for(int i=0;i<n;i++) for(int j=0;j<m;j++){
scanf("%lf",&matrix[i][j]);
summs[i] += matrix[i][j];
}
int type = 0;
printf("Введите 0– по возрастанию, не 0– по убыванию: ");
scanf("%d",&type);
int flag = 1;
while(flag){
flag = 0;
for(int i=0;i<n-1;i++)
if((!type&&(summs[i] > summs[i+1]))||
( type&&(summs[i] < summs[i+1]))){
double *ptr = matrix[i], sum = summs[i];
matrix[i] = matrix[i+1]; summs[i] = summs[i+1];
matrix[i+1] = ptr; summs[i+1] = sum;
flag = 1;
}
}
puts("Результат:");
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) printf("%6.2lf ",matrix[i][j]);
free(matrix[i]);
printf("\tSumma: %.3lf\n",summs[i]);
}
free(matrix); free(sums);
return 0;
}
Пример 4
Создать в динамической памяти массив строк. Строки вводятся пользователем, признак завершения ввода – ввод пустой строки. Длина каждой строки не превышает 100 символов. Удалить из массива все строки, длина которых меньше средней длины всех введенных строк. Полученный массив вывести на экран. При реализации обеспечить эффективное хранение строк в памяти: память под строки выделяется динамически, с учетом длины строки.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[])
{
char **list = NULL;
int count = 0, midlen = 0;
puts("Вводите строки”);
while(1){
char str[101];
gets(str);
if(strcmp(str,"")==0) break;
char **tmp = (char**)realloc(list, (count+1)*sizeof(char*));
if(!tmp) {puts("Мало памяти!"); break;}
list = tmp;
list[count] = (char *)malloc(strlen(str)+1);
if(!list[count]) {puts("Мало памяти!"); break;}
midlen += strlen(str); strcpy(list[count],str); count++;
}
midlen /= count;
for(int i=0;i<count;i++)
if(strlen(list[i]) < midlen){
free(list[i]);
memcpy(&list[i],&list[i+1],(count-i-1)*sizeof(char*));
count--;
i--;
}
list = (char **)realloc(list,count*sizeof(char*));
puts("Результат: ”);
for(int i=0;i<count;i++){
puts(list[i]); free(list[i]);
}
free(list);
return 0;
}