第一天交给老师的报告。

2017年11月23日23:27:13 4 339 views

昨天被老师要求要写每日的报告交给老师,一天干了什么事,做了什么,现在严格把控我们的学习进度,然后第一天,他就有事忙,而我也有事吗,一下午到晚上就没干过什么事。就上午看了一下算法,解了一道题。然后为了凑报告,把昨天的部分内容放进去了。

一下内容是word文档直接插入的。

贪心算法

我的理解是:像枚举一样,把所有可能找出来,但是每次都选择都选择最优的路径。

网络上的解释是:贪心法:即每次选择最优值,从而达到全局最优的方法,它是从问题的某一个初始解出发,向给定的目标递推。推进的每一步做一个当时看似最佳的贪心选择,不断地将问题实例归纳为更小的相似的子问题,并期望通过所作的局部最优选择产生一个全局最优解。

典型的问题就是删数问题:

题目:

键盘输入一个高精度的正整数n(<=240位),

去掉任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。

编程对给定的n和s,寻找一种方案,使得剩下的数最小。

Simple Input

178543

4

Simple Output

13

自己的思路解析:

java中最大能支持19位的整数,而要求是240位的数,这是不可能实现的,所有我用字符串来接收,对于字符,这个长度可以忽略的。

又因为在java中有个可变字符,StringBuffer。对于这题,就用不着对String做删除字符的炒作了,用StringBuffer更方便,里面还提供deleteCharAt的方法,直接删除某个位子的字符。

所以就定义一个字符串n,然后要删除int型s。

代码进行S此循环,每次删除数字最大的数字符。

实现代码:

ACM题

给定一个十进制整数N,求其对应2进制数中1的个数

解题思路:

看了这题还是比较简单,在考虑它的输入形式花费了一定得时间。对于java来说,这种题就是直接调用对象来完成很是轻松。传入一个整数N,然后直接转换成二进制字符串,定义个sum变量,用if判断,利用String的charAt方法,获取每个字符与字符“1”比较,如说if成立,就sum++。完成后输出次数。

实现代码:

ACM题

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?

此题还是复杂,最开始用数学的排列组合,做出来后,答案明显不对,但是仔细分析这题也是组合问题,只是给了不同的条件。

解题思路:

  1. 把盘子分成两种情况,1种是容许空盘子的情况,一种是不容许空盘子的情况。
  2. 空盘子的情况就是,最少就可能有1个空盘子。所以(N-1)形式去递归,当盘子只剩一个的时候,那时就是只有各种方法,把所有苹果放在一个盘子里,此时就该return。
  3. 不会有空盘子的情况,就是每个盘子都会有苹果,那么就是(M-N)这样一次去放入,放到最后一个也就只有一种方法,此时返回。
  4. 还有一中情况就是,当盘子数量大于苹果数量的时候,N>M。这个时候就相当于是M个盘子在进行找方法,所有就有(M,M)直接把盘子个数变成苹果的数量。
  5. 综合上面的情况的方法就有,(N-1)+(M-N),(M,M)属于(M-N)里的。
  6. 此题用到了递归和分治算法(我可能是这样理解分治的)

实现代码:

 



欢迎来到菜鸟头头的个人博客,下方有我的微信二维码,有兴趣的朋友可以加我好友,咱们一起交流探讨。
  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的支付宝红包
  • 支付宝红包扫一扫打赏
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:4   其中:访客  2   博主  2

    • avatar 姜辰 3

      专业人士。膜拜

        • avatar 头头 Admin

          @姜辰 有撒膜拜,互相膜拜。

        • avatar 威客系统 1

          这是实习报告吗