英国华人论坛 英国IT业找工作面试题

英国论坛

友情提示 递归算法简单但速度慢

  请在两天内作答。

  Elixent’s Placement Problem

  Write a program (in C or C++) that places an arbitrary netlist represented as a directed graph G = (V, E) with vertices V and edges E over a 1D array of N processors:

  p_1 p_2 p_3 ... p_N

  Each vertex should be placed on a single processor and no processor can hold more than one vertex (you can assume there are as many processors as you need). For example vertex v_1 might be placed on processor p_1 and v_2 on p_4:

-----------

  v_1 v_2

  p_1 p_2 p_3 p_4 ... p_N

  If there were an edge between v_1 and v_2, then it would automatically be routed along the 'shortest' path between the respective processors (as shown). The distance of this edge is 4-1 = 3. The cost of an overall placement is simply the sum of all edge distances. Placements with lower cost as these are 'better', but the computational complexity of your placement algorithm also matters (you might need to place very large netlists).

  The graph should be read in from standard input in the form

  10

  1,3 2,4 4,5 ...

  In the first line '10' gives the number of vertices, the second line defines which pairs of vertices are connected by edges (the first vertex is numbered 1).

  The program should output the placement cost and results on standard output, giving the vertex allocated to each processor in turn, or - if a processor is empty. For example:

  21

  2 4 - 3 1 ...

  would mean the placement cost was 21 and vertex 2 was allocated to p_1, 4 to p_2, p_3 was empty, 3 to p_4 etc.

  You might optionally want to consider a more complex problem with a non-linear notion of cost that accounts for congestion in the case when there are multiple overlapping edges. For example, the cost function could be redefined as the sum of the squares of the number of edges spanning each pair of neighbouring processors. In this case the following configuration of edges:

--- ---

  p_1 p_2 p_3 p_4 p_5 .... p_N

  would have cost:

  1 edge spanning p_1 to p_2

  2^2 edges spanning p_2 to p_3

  1 edge spanning p_3 to p_4

  1 edge spanning P_4 to p_5

  ---

  7

  Again, lower cost is better, but computational complexity also matters.

英国留学

 ·英国新闻 英国男拴了只海鸥在马路上遛,致使海鸥死亡。网友:几乎变态
·英国新闻 你在英国丢过手机吗?伦敦均匀每6分钟被偷一部手机...
·分类市场 居家电商客服时间自在薪资高
·分类市场 North Finchley 大双人房
 ·澳洲新闻 多名自由党议员被控受贿,廉政公署突击搜查新州前州长胞弟住
·澳洲新闻 澳洲五星级餐厅最多的地方在哪里?墨尔本排名第一,西悉尼成
英国留学可以补申吗?怎么补申?
英国英国留学

英国留学可以补申吗?怎么补申?

英国中文论坛英国的留学申请是分几轮进行申请的。对于赶上了第一轮申请的同学,如果对自己第一轮的申请不是很满意,之后还能不能去补申?今天我们就一起来看看 英国留学申请如何补申 吧! ...

英国G5大学留学A-Level成绩要求是多少?
英国英国留学

英国G5大学留学A-Level成绩要求是多少?

英国中文论坛对英国方向的预备留学生们而言,英国G5大学有着不可撼动的王者地位。英国G5大学,是英国最高研究水平和学术水平的代表,包括牛津大学、剑桥大学、伦敦政治经济学院、帝国理工学 ...

英国名校TESOL专业申请条件是什么?
英国英国留学

英国名校TESOL专业申请条件是什么?

英国中文论坛英国名校TESOL专业申请条件是什么?TESOL证书是全球公认的ESL( 教授英语为第二语言 ) 教师职业资格证书。拥有TESOL证书,就拥有了在世界各国从事以英语为第二语言的教学资格。但是T ...

留学英国硕士一年到底能学些什么?
英国英国留学

留学英国硕士一年到底能学些什么?

英国中文论坛留学英国硕士一年,真正上课9月到第二年6月,除去圣诞复活节及各种周末,真正在学校上课的时间大概也就6个月,第二年6月之后的时间基本就留给你写论文了,所以官网上挂着说有三 ...

申请英国硕士会接受非本科学历吗
英国英国留学

申请英国硕士会接受非本科学历吗

英国中文论坛英国硕士教育优良,课程也是非常高端,值得推荐,很多专科生或者没有本科学历的学生想要申请英国硕士留学,但是英国硕士留学院校可以接受国内非本科学生吗?下面小编为大家详细 ...

英国留学申请签证注意事项有哪些?
英国英国留学

英国留学申请签证注意事项有哪些?

英国中文论坛去留学,很重要的材料就是签证了。办理英国留学签证注意事项有哪些?下面是小编整理的英国留学签证办理注意事项,一起来看看吧。 1、英国签证申请中心跟英国使馆或领事馆有何关 ...