2023-06-24:给你一根长度为 n 的绳子, 请把绳子剪成整数长度的 m 段, m、n都是整数,n > 1并且m > 1, 每段绳子的长度记为 k[0],k[1]...k[m - 1]。 请问
2023/6/24 18:52:52
本文主要是介绍2023-06-24:给你一根长度为 n 的绳子, 请把绳子剪成整数长度的 m 段, m、n都是整数,n > 1并且m > 1, 每段绳子的长度记为 k[0],k[1]...k[m - 1]。 请问,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2023-06-24:给你一根长度为 n 的绳子,
请把绳子剪成整数长度的 m 段,
m、n都是整数,n > 1并且m > 1,
每段绳子的长度记为 k[0],k[1]...k[m - 1]。
请问 k[0]k[1]...*k[m - 1] 可能的最大乘积是多少?
例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
答案需要取模1000000007。
输入: 10。
输出: 36。
答案2023-06-24:
具体步骤如下:
1.如果n <= 3,返回n-1。
2.如果n > 3,计算剩下绳子长度为n - 4,此时剩下的长度为4。
3.如果剩下的长度为0,即n为3的倍数,最后一段长度为1;如果剩下的长度为2,最后一段长度为2;如果剩下的长度为4,最后一段长度为4。
4.计算3的个数,即rest = n - (剩下的长度);计算最后一段的长度last。
5.利用快速幂算法计算3的rest/3次方取mod后的结果,记为power(3, rest/3)。
6.返回(power(3, rest/3) * last) % mod作为最大乘积的结果。
例如,当n为10,按照上述步骤计算:
1.n > 3且不是3的倍数,剩下的长度为2,最后一段长度为2。
2.计算3的个数,rest = n - 2 = 8。
3.计算power(3, rest/3) = power(3, 8/3)。
4.返回(power(3, 8/3) * 2) % mod,计算结果为36,即最大乘积。
因此,输入为10,输出为36。
该代码的时间复杂度为O(log(n)),空间复杂度为O(1)。
在函数power
中,通过快速幂算法计算x的n次方,时间复杂度为O(log(n))。在函数cuttingRope
中,没有使用任何循环或递归,只有一些简单的判断和计算操作,因此时间复杂度为O(1)。
对于空间复杂度,代码只使用了常数级别的额外空间来存储变量,因此空间复杂度为O(1)。不随输入规模的增加而增加。
go完整代码如下:
package main import "fmt" const mod = 1000000007 // power计算x的n次方,取mod后的结果 func power(x int, n int) int { ans := int64(1) x64 := int64(x) n64 := int64(n) for n64 > 0 { if n64&1 == 1 { ans = (ans * x64) % mod } x64 = (x64 * x64) % mod n64 >>= 1 } return int(ans) } // cuttingRope根据观察得到的规律计算绳子的最大乘积 func cuttingRope(n int) int { if n == 2 { return 1 } if n == 3 { return 2 } rest := 0 last := 0 if n%3 == 0 { rest = n last = 1 } else if n%3 == 1 { rest = n - 4 last = 4 } else { rest = n - 2 last = 2 } return (power(3, rest/3) * last) % mod } func main() { n := 10 result := cuttingRope(n) fmt.Println("Result:", result) }
rust完整代码如下:
const MOD: i32 = 1_000_000_007; fn power(x: i32, n: i32) -> i32 { let mut ans: i64 = 1; let mut x: i64 = x as i64; let mut n: i64 = n as i64; while n > 0 { if n & 1 == 1 { ans = (ans * x) % MOD as i64; } x = (x * x) % MOD as i64; n >>= 1; } ans as i32 } fn cutting_rope(n: i32) -> i32 { if n == 2 { return 1; } if n == 3 { return 2; } let rest = if n % 3 == 0 { n } else if n % 3 == 1 { n - 4 } else { n - 2 }; let last = if n % 3 == 0 { 1 } else if n % 3 == 1 { 4 } else { 2 }; ((power(3, rest / 3) as i64 * last as i64) % MOD as i64) as i32 } fn main() { let n = 10; let result = cutting_rope(n); println!("Result: {}", result); }
c++代码如下:
#include <iostream> using namespace std; const int mod = 1000000007; // power计算x的n次方,取mod后的结果 long long power(long long x, int n) { long long ans = 1; while (n > 0) { if ((n & 1) == 1) { ans = (ans * x) % mod; } x = (x * x) % mod; n >>= 1; } return ans; } // cuttingRope根据观察得到的规律计算绳子的最大乘积 int cuttingRope(int n) { if (n == 2) { return 1; } if (n == 3) { return 2; } int rest = 0, last = 0; if (n % 3 == 0) { rest = n; last = 1; } else if (n % 3 == 1) { rest = n - 4; last = 4; } else { rest = n - 2; last = 2; } return (int)((power(3, rest / 3) * last) % mod); } int main() { int n = 10; int result = cuttingRope(n); cout << "Result: " << result << endl; return 0; }
c完整代码如下:
#include <stdio.h> const int mod = 1000000007; // power计算x的n次方,取mod后的结果 long long power(long long x, int n) { long long ans = 1; while (n > 0) { if ((n & 1) == 1) { ans = (ans * x) % mod; } x = (x * x) % mod; n >>= 1; } return ans; } // cuttingRope根据观察得到的规律计算绳子的最大乘积 int cuttingRope(int n) { if (n == 2) { return 1; } if (n == 3) { return 2; } int rest = 0, last = 0; if (n % 3 == 0) { rest = n; last = 1; } else if (n % 3 == 1) { rest = n - 4; last = 4; } else { rest = n - 2; last = 2; } return (int)((power(3, rest / 3) * last) % mod); } int main() { int n = 10; int result = cuttingRope(n); printf("Result: %d\n", result); return 0; }
这篇关于2023-06-24:给你一根长度为 n 的绳子, 请把绳子剪成整数长度的 m 段, m、n都是整数,n > 1并且m > 1, 每段绳子的长度记为 k[0],k[1]...k[m - 1]。 请问的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?