[请益] 外商面试时的一道程式考题(求解)

楼主: kimjay (kim)   2014-09-05 09:13:55
有一个问题想请教板上各位先进,
这是朋友的弟弟当完兵后,今年6月去应征外商一个做应用程式开发的部门,
朋友弟弟在面试时,遇到的其中一个题目
(刚好聊到,我想尝试自己解解看,可是写了好几次都解不出来)
因为并没有指定特定语言,我又想知道这题该如何解?所以不知道PO在科技版合不合适?
听他说主要是考面试者的基本程式设计和逻辑,以及表达能力
题目内容大概照他说的大概描述如下
--------------------------------
1.(考基本程式设计和逻辑)
假设有N个人排队来领号码牌,领的号码牌是1-N号,接下来要从N个人挑7个人入选
(也就是说排队的人只是先取得资格,中选的人是另由程式挑选)
排序规则如下,请依题目撰写程式(使用程式语言不限)。
从N个号码挑选一个起始号码,以及一个间隔号码,共取7个人,超过N则从头开始算起
已被取出的号码就不会在数列中(注:非随机取乱数)
2.(考表达能力)
根据题目描述部份,如果今天您要向客户主管说明这个取号游戏规则,您要如何向客户主管举例说明
(把客户主管当做不会程式的笨蛋,但要使其了解)
---------------------------
1.
假设N=9,起始号码=3,间隔码号=3,挑选人数=7
那么取出的号码顺序如下:
3、6、9、4、8、5、2
2.
假设N=10,起始号码=3,间隔码号=3,挑选人数=7
那么取出的号码顺序如下:
3、6、9、2、7、1、8
3.
假设N=11,起始号码=3,间隔码号=3,挑选人数=7
那么取出的号码顺序如下:
3、6、9、1、5、10、4
------------------------
以上,就是程式写完后应得出的结果,也就是在已知N的状况下,
不管其他起始号码、间隔码号、挑选人数这些变量如何变动
是有规则的取出顺序号码,想请问此题的解题技巧在哪里?
知道其概念,但程式解不出来= =||
打了好几次,pietty都当掉,后来直接先打好先贴上了~
作者: b941152 ( )   2014-09-05 09:24:00
写一个矩阵用做判别,当取过之后把该位置的数字归零当再遇到归零的数字之后再往下取 直到有非零的数字?
作者: theone777 (你想要什么)   2014-09-05 09:25:00
浅见,mod,注意边界
作者: b941152 ( )   2014-09-05 09:26:00
@@ 临时想到的... 应该有高手可以帮忙
楼主: kimjay (kim)   2014-09-05 09:32:00
mod取余数~和发扑克牌程式一样,但是他是有规则取出,并非乱数随机,我一开始有想到,但发现有问题还是我哪里做错了吗?
作者: a7904120 (pubear)   2014-09-05 10:50:00
hashtable collision?
作者: manlike ( )   2014-09-05 10:57:00
楼上这样乱烙专有名词不行噢~大概就用个queue存1~N, 然后开始选, 没选到的就dequeue再enqueue, 然后一直选, 直到选完或者queue空了。queue可以用array做或是linked list, 用array可以发挥到极致, 就一直 mod 和 memecpy。*memcpy
作者: a7904120 (pubear)   2014-09-05 11:53:00
我觉得概念满像的呀~~
作者: jojowolf (天使羽根)   2014-09-05 13:30:00
目前想到linked list可解,元素断开链结也很方便
作者: steve422 (steve422)   2014-09-05 13:51:00
我用python写好了
作者: saladim (杀拉顶)   2014-09-05 13:57:00
mod 有 cycle问题 要小心一点这个在需求那边没定义
作者: zenuo (坚持到底永不放弃)   2014-09-05 18:09:00
N可以被间隔整除时就会循环,此时当取到的数大于N时 余数+1
作者: boss0405 (boss)   2014-09-05 18:38:00
用linked list写个queue就可以了y
作者: buletris (◆爱发呆◇)   2014-09-05 19:00:00
小弟我会这样写~http://ppt.cc/PWIx表达就想像10个人排列分别又左至右别1号到10号的号码牌随机挑到第三位出列后, 顺时针下一位接序报数1再下一位报2 每报到3就出列, 直到出列数达7人为止依序看出列顺序看号码牌即为排列顺序补充报到3 下一位再从1开始报起
作者: kimiyuan (kimiko)   2014-09-05 21:06:00
这题算很简单吧…他快把algorithm说完了照题目就能直接 coding
作者: sam9595 (帕帕)   2014-09-06 03:24:00
bule的解法并没有想到间隔很大会跑得极慢的问题我不会说很简单 有一堆细节没有经验的人是不会注意到的
作者: futureq (无名再见)   2014-09-06 09:11:00
去看算法的书吧不过名字忘记了,囧。
作者: longlongint (华哥尔)   2014-09-06 22:12:00
约瑟夫问题直接解可用阵列 高速解用余数可是要查一下资料OTZ

Links booklink

Contact Us: admin [ a t ] ucptt.com