当前位置：首页 > news >正文

三元组的最短距离

news 来源：原创 2024/6/28 14:00:26

前言

个人小记

一、简介

定义三元组（a,b, c）（a,b,c 均为正数）的距离 D=|a-b|+|b-c|+|c-a|。给定 3 个非空整数集合 S1, S2 ,S3, 按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组（a, b, c）（a∈S1,b∈S2,c∈S3）中的最小距离。例如 S1={-1, 0, 9}, S2={-25，-10，10，11}，S3={2，9，17，30，41}，则最小距离为 2，相应的三元组为（9，10，9）。

二、代码

#include<stdio.h>
#include <stdlib.h>typedef struct Queue
{int *data;int size,count,head,tail;
}Queue;Queue* init_queue(int n)
{Queue* Q=(Queue*)malloc(sizeof(Queue));Q->data=(int*)malloc(sizeof(int)*n);Q->size=n;Q->head=0;printf("请输入元组的值:");for(int i=0;i<n;i++){scanf("%d",&(Q->data[i]));}Q->count=n;Q->tail=n-1;return Q;
}int pop(Queue* Q)
{if(Q->count==0){printf("队列为空,无法pop\n");return 0;}Q->count-=1;Q->head+=1;if(Q->head==Q->size)Q->head=0;return 1;
}int search(Queue* Q)
{if(Q->count==0){printf("队列为空,无法查看\n");return 0;}return Q->data[Q->head];
}void clear_queue(Queue* Q)
{if(Q==NULL)return ;free(Q->data);free(Q);return ;
}void swap(int *a,int *b)
{int t=*a;*a=*b;*b=t;return ;
}int Min(int a,int b,int c)
{if(a>b)swap(&a,&b);if(a>c)swap(&a,&c);return a;
}void func(Queue* a,Queue* b,Queue* c)
{int min=0x7fffffff;int d[3];while(a->count!=0&&b->count!=0&&c->count!=0){int ma=search(a),mb=search(b),mc=search(c);int M=abs(ma-mb)+abs(mb-mc)+abs(ma-mc);if(M<min){min=M;d[0]=ma,d[1]=mb,d[2]=mc;}int d=Min(ma,mb,mc);if(ma==d)pop(a);if(mb==d)pop(b);if(mc==d)pop(c);}printf("三元组的最小值为:%d\n",min);printf("三元组为(%d,%d,%d)\n",d[0],d[1],d[2]);return ;
}int main()
{int a,b,c;printf("请输入三元组各自的长度:");scanf("%d%d%d",&a,&b,&c);Queue* Qa=init_queue(a);Queue* Qb=init_queue(b);Queue* Qc=init_queue(c);func(Qa,Qb,Qc);clear_queue(Qa);clear_queue(Qb);clear_queue(Qc);return 0;
}

二、结果

请输入三元组各自的长度:3 4 5
请输入元组的值:-1 0 9
请输入元组的值:-25 -10 10 11
请输入元组的值:2 9 17 30 41
三元组的最小值为:2
三元组为(9,10,9)
sjq@SEER:~/coding$ ./a.out 
请输入三元组各自的长度:2 3 4
请输入元组的值:1 2
请输入元组的值:3 4 5
请输入元组的值:3 4 5 6
三元组的最小值为:2
三元组为(2,3,3)