2 wb coder wb_coder 于 2017.09.10 17:04 提问

最近一些笔试 算法题

问几个最近遇到的几个编程题(求算法):

1.给n个学生,每个学生有一个值m,-50<=m<=50,从中选k个学生,要求相邻学生的编号差小于d,使得k个学生m值的积最大如
输入(第一行为n,第二行为m值,第3行为k,d)
3
7 4 7
2 50
这个算法怎么写呀(主要是m有时候会为负值,动态规划肯定能解),各位大神
拜托给个算法
2.给一个n,求1<=a,b,c,d<=n,使得a^b=c^d成立的个数,如n=1,1^1=1^1,最后输出1,这个有没有谁做过,能给个不超时的算法吗?(自己写的4个循环的嵌套,超时了,然后我就改成了一个递归的,分两步先算a,b,c,d中不带n的这个就等于给n-1的值再算a,b,c,d中含n的但是结果有不对)

5个回答

wb_coder
wb_coder   2017.09.10 17:53

这个算法怎么写呀,好像是最大字段和,但是又不是,有没有大神可以给个算法的

qq_40182366
qq_40182366   2017.09.10 19:11

第一題我比較看不懂
第二題比較簡單(不知道算不算作弊)
等號要成立,a與c之間應該會有次方關西(a^x=c),而b與d之間會有因倍數關係(b=d*x)
而且這兩個關西相對,例如(a^3=c)那(b*3=d)
簡單的說起來,對於一個a,能找到幾個c(不超過n),對於找好的ac,又有幾個b(不超過n)
再把所有a的結果數量進行加總,三個循環
應該可以

希望你看得懂繁體

tjk123456
tjk123456   2017.09.10 22:13

刚入门,关于第一个我从数学上给点思路,不知道能不能行,
积要最大,则负数要求成对。

关于算法还没有涉及多少,粗暴点的方法(我假设的m值为整数)
将n个学生的m值按从50到0和从-50到0分入两个数组
从最大正数和最小负数开始取,共取k个值,得到最大积s
判断得到s的数是否符合条件,相邻学生的编号小于d,符合则该积为最大
不符合则往下取

第一轮默认了直接取最大绝对值,当第一轮取数均不能满足条件,则放弃最大绝对值,以第二大绝对值开始

chanshimudingxi
chanshimudingxi   2017.09.11 08:25

1-问题是n个数选择m个数的问题。定义子问题为max(i)(j):选择j个数,以第i个数结尾的最大乘积.min(i)(j):选择j个数,以第i个数结尾的最小乘积。max(i)(j)=max(k)(j-1)*a[i]和min(k)(j-1)*a[i]两者中最大.1<=k<=i-1。min同理。

chanshimudingxi
chanshimudingxi   2017.09.11 09:20

2-全部二进制表示。考虑x^y结果的性质,如果等于1,只有1种。如果等于10,那么2种。如果等于11,那么1种。如果等于100,那么4种。是如果等于101,那么2种。规律等于二进制表示有多少个0就有多少2的多少次幂种,还有就是去掉大于范围n的那些情况。
比如n为6。在考虑二进制100的时候,100^100=100^101=100^110=100^111,最后111就不能考虑,只有3种。

Csdn user default icon
上传中...
上传图片
插入图片