sopherwenxin学习笔记

刀锋上的舞者: 我是风中的落叶，看我如何飞翔
posts - 5, comments - 8, trackbacks - 0, articles - 1

第三届全国高校程序设计大赛赛题问题5：导线交叉

Posted on 2006-01-14 18:08 sopherwenxin 阅读(1315) 评论(7)  编辑 收藏 引用 所属分类: 编程札记

  

问题5：导线交叉 

一个接线箱中上下各有n个端子，顶部的每个端子分别与底部的某个端子相连，形成一个完美匹配。

由于端子匹配的不同，导线会产生各种可能的交叉。在如下的例子中导线交叉点共有22个：

 t_2.bmp
编一个程序计算给定的连线方式下导线交叉点的总数。 

输入：

第一行含1个整数，表示实例个数。

每个实例有一行输入，含n个整数，第i个整数表示与顶部第i个端子相连接的底部端子的编号(1≤i≤n)。每个整数用空格隔开。 

输出：

第一行含1个整数，表示实例的序号

第二行输出交叉点的个数。

样例输入（采用上图中的例子）

1

10

8  7  4  2  5  1  9  3  10  6 

相应的正确输出样例：

1

22    

Feedback

# re: 第三届全国高校程序设计大赛赛题问题5：导线交叉   回复  更多评论   

2006-01-14 20:49 by hnhls99
这个并不复杂，其实很简单的。就是判断一下上一排端子右侧的端子相连的下一排的端子是否小于他相连的端子，小于就相交。

# re: 第三届全国高校程序设计大赛赛题问题5：导线交叉   回复  更多评论   

2006-01-15 10:37 by sopherwenxin学习笔记
To hnhls99 :
上面结论不难得出，还要考虑的一个问题就是是交叉点重复得个数。也就是说最后得出的交叉点总数必须减掉重复的点。

# re: 第三届全国高校程序设计大赛赛题问题5：导线交叉   回复  更多评论   

2006-01-15 10:58 by 可冰
看题好像没有计算重复点吧,如果计算的话上面的图中的交点数可能就不够22个了.
如果要计算的话,我想可以用方程来表示线,计算出每个交点的坐标来.

# re: 第三届全国高校程序设计大赛赛题问题5：导线交叉   回复  更多评论   

2006-01-15 21:22 by hnhls99
To 学习笔记：
有没有比较简单的方法去计算重复的点呢？

# re: 第三届全国高校程序设计大赛赛题问题5：导线交叉   回复  更多评论   

2006-01-16 10:12 by sopherwenxin学习笔记
用方程计算比较麻烦，要自己定义坐标系，计算方程的解。可以保证的一点是肯定可以实现。可能这种方法就是最简单的了。

# re: 第三届全国高校程序设计大赛赛题问题5：导线交叉   回复  更多评论   

2006-03-26 11:50 by Tauruser
可以根据相似三角形的性质很简单了推出，交点的高和水平位置，再根据这个来判断交点是否重合，这样应该比解方程简单点。

# re: 第三届全国高校程序设计大赛赛题问题5：导线交叉   回复  更多评论   

2007-05-18 12:59 by guoke
#include<stdio.h>
#include<malloc.h>
void main()
{
int n,m,i,j,k,count=0;
int *a;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&n);
a=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(j=0;j<n;j++)
{
for(k=j+1;k<n;k++)
{
if(a[j]<a[k]) count++;
}
}
printf("%d\n%d\n",i,count);
}

}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理