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
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
IT公司笔试之精选30道Java笔试题解答
都是一些非常非常基础的题,是我最近参加各大IT公司笔试后靠记忆记下来的,经过整理献给与我一样参加各大IT校园招聘的同学们,纯考Java基础功底,老手们就不用进来了,免得笑话我们这些未出校门的孩纸们,但是IT公司就喜欢考这些基础的东西,所以为了能进大公司就~~~当复习期末考吧。花了不少时间整理,在整理过程中也学到了很多东西,请大家认真对待每一题~~~ 出处:博客园 下面都是我自己的答案非官
整理一些笔试题(要求手写代码的)
1、将一整数逆序后放入一数组中(要求递归实现) void convert(int *result, int n) { if(n>=10) convert(result+1, n/10); *result = n%10; } int m
腾讯2018实习生笔试编程题 三
一、题目描述:小Q的公司最近接到m个任务,第i个任务需要xi的时间去完成,难度等级为yi。小Q拥有n台机器,每台机器最长工作时间zi,机器等级wi。对于一个任务,它只能交由一台机器来完成,如果安排给它的机器的最长工作时间小于任务需要的时间,则不能完成,如果完成这个任务将获得200*xi+3*yi的收益。对于一台机器,它一天只能完成一个任务,如果它的机器等级小于安排给它的任务难度等级,则不能完成。小...
C语言笔试算法题
C语言笔试算法题
常见数据结构与算法笔试面试题大荟萃
本人花几个月在多个优秀博客总结整理出来的,希望对大家有用。
刚网上测评了算法工程师的笔试,才发现自己的编程有多烂!
平心而论,题目不是很复杂,基本都三言两语交代清楚,可自己就是毫无头绪,还是平时做得少,练得少。 编程题透一下,有两道不会做: 1.序列模式匹配问题,给定一个输入文本text,和一个待匹配文本pattern,要求在text文本中匹配到的pattern的最短字符串,匹配结果可不连续,例如输入text为:abaacxbcbbbacc,pattern为cbc,则匹配为:abaacxbcbbbbacc。
网易实习生笔试编程题 二叉树
有一棵二叉树,树上每个点标有权值,权值各不相同,请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1,一个节点经过多少条边到达另一个节点为这两个节点之间的距离。 给定二叉树的根节点root,请返回所求距离。 import java.util.*; /* public class TreeNode { int val = 0;
精选30道Java笔试题解答
都是一些非常非常基础的题,是我最近参加各大IT公司笔试后靠记忆记下来的,经过整理献给与我一样参加各大IT校园招聘的同学们,纯考Java基础功底,老手们就不用进来了,免得笑话我们这些未出校门的孩纸们,但是IT公司就喜欢考这些基础的东西,所以为了能进大公司就~~~当复习期末考吧。花了不少时间整理,在整理过程中也学到了很多东西,请大家认真对待每一题~~~   下面都是我自己的答案非官方,仅供参考,如
2016京东算法工程师实习生笔试编程题:小球的距离
小东和三个朋友一起在楼上抛小球,他们站在楼房的不同层,假设小东站的楼层距离地面N米,球从他手里自由落下,每次落地后反跳回上次下落高度的一半,并以此类推知道全部落到地面不跳,求4个小球一共经过了多少米?(数字都为整数) 给定四个整数A,B,C,D,请返回所求结果。 测试样例: 100,90,80,70 返回:1020 解题思路:递归解决。 代码:
2016腾讯实习生笔试编程题:构造回文
给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢? 输出需要删除的字符个数。 输入描述: 输入数据有多组,每组包含一个字符串s,且保证:1 输出描述: 对于每组数据,输出一个整数,代表最少需要删除的字符个数。 输入例子: abcda google 输出例子: 2 2 解题思路