找回密码
 欢迎注册
查看: 19299|回复: 2

[讨论] 算法题

[复制链接]
发表于 2020-4-28 12:11:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
1、各元素均大于1的正整数列表最少可以划分成几个子列表,划分规则是:1、连续的几个元素可以组成一个子列表,如果首尾元素有大于1的公约数;2、各子列表无重叠部分;3、单独的一个元素可以是一个子列表
    例如(2,3,3,2,3)最少可以划分成2个子列表。(2),(3,3,2,3)或(2,3,3,2),(3)
         (7,11,7,19,7,17,11,19)最少可以划分成2个子列表(7,11,7),(19,7,17,11,19).



2、一个L*W(均为正整数)的矩形最少可以由多少个正方形(边长为任意正整数)组成?



3、字符串由1~9字符组成,对于任意字符串如何找出所有位置配对(i,j),使得从i到j位组成的数字是2019的倍数。
    如“1817181712114”,结果(1,5)对应18171,(5,9)对应18171,(9,13)对应12114都是2019的倍数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-4-30 00:31:10 | 显示全部楼层
3          2019=3 * 673,对于i-j可以先判断是否3的倍数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-4-30 13:01:20 | 显示全部楼层
2应该很难有很好的算法。
3完全穷举复杂度也不高,对于长度为n的情况,穷举复杂度只用O(n^2)
第一个可以动态规划,在O(n^2)复杂度内完成。
假设我们对于任意k<=m都已经得到前k个元素的最小划分数目f(k),并且设f(0)=0,于是对于第m+1个数可以有伪码
  1.    best_len=m+1;
  2.    for(i=1; m;i++){
  3.          if(gcd(x_i, x_{m+1})>1){
  4.                if(f(i-1)+1<best_len){
  5.                    best_len=f(i-1)+1;
  6.                }
  7.          }
  8.    }
  9.    f(m+1)=best_len;
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-12-4 01:34 , Processed in 0.025187 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表