|
>学习工控知识，就来工控小新
农历十一月十一日 2024/01/ 01
往期推荐
2023年12月28日，每日花费一分钟练习C语言
2023年12月27日，每日花费一分钟练习C语言
每
日
一
练
/ Daily Exercises
题目：
字符串相乘
给定两个以字符串形式表示的非负整数num1和num2返回num1和num2的乘积，它们的乘积也表示为字符串形式。
示例 1: 输入: num1=“2"，num2 =“3" 输出:"6"
示例 2: 输入: num1=“123"，num2 =“456"输出:“56088"
说明:
1.num1和num2的长度小于110。
2.num1和num2 只包含数字0-9。
3.num1和num2均不以零开头，除非是数字0本身。
4不能使用任何标准库的大数类型(比如Biglnteger)或直接将输入转换为整数来处理。
题目分析
题目要求我们给定两个以字符串形式表示的非负整数num1 和 num2，返回 num1 和 num2的乘积，它们的乘积也表示为字符串形式。输入是两个非空字符串，输出是一个字符串。我们不能使用任何标准库的大数类型或直接将输入转换为整数来处理，因为输入可能超过整数的范围。
我们可以用一个类似于竖式乘法的方法来解决这个问题，即从右到左遍历num1 的每一位，与 num2的每一位相乘，得到一个临时的结果，然后将这些临时的结果按照位数相加，得到最终的结果。为了方便计算，我们可以用一个数组来存储最终的结果，数组的长度为 num1的长度加上 num2 的长度，因为两个 n 位数的乘积最多为 2n 位数。我们可以用一个循环来遍历 num1 的每一位，对每一位，再用一个循环来遍历 num2的每一位，对每一位，将它们相乘，得到一个两位数，将这个两位数的个位和十位分别加到数组的对应位置，注意要处理进位的情况。最后，我们将数组转换为字符串，去掉前导的零，返回结果。这种方法的时间复杂度是O(mn)，空间复杂度是 O(m+n)，其中 m 和 n 是 num1 和 num2 的长度。
程序展示
根据上述的分析，我们可以用以下的C语言程序来实现题目的要求。该程序在VC6.0的环境下运行正常，输入两个非空字符串，输出它们的乘积，也是一个字符串。
#include <stdio.h>#include <string.h>#include <stdlib.h>
// 定义一个函数，给定两个以字符串形式表示的非负整数 num1 和 num2，返回它们的乘积，也是一个字符串char* multiply(char* num1, char* num2) { int m = strlen(num1); // 获取 num1 的长度 int n = strlen(num2); // 获取 num2 的长度 int len = m + n; // 计算结果的最大长度 int* res = (int*)malloc(len * sizeof(int)); // 分配一个数组，用来存储结果的每一位 memset(res, 0, len * sizeof(int)); // 初始化数组为0 int i, j; for (i = m - 1; i >= 0; i--) { // 从右到左遍历 num1 的每一位 for (j = n - 1; j >= 0; j--) { // 从右到左遍历 num2 的每一位 int mul = (num1 - '0') * (num2[j] - '0'); // 将两位相乘，得到一个两位数 int p1 = i + j; // 计算这个两位数的十位在数组中的位置 int p2 = i + j + 1; // 计算这个两位数的个位在数组中的位置 int sum = mul + res[p2]; // 将这个两位数的个位和数组中的原来的值相加，得到一个新的值 res[p1] += sum / 10; // 将新值的十位加到数组中的对应位置，注意要处理进位 res[p2] = sum % 10; // 将新值的个位存到数组中的对应位置 } } char* ans = (char*)malloc((len + 1) * sizeof(char)); // 分配一个字符串，用来存储结果 int k = 0; // 定义一个指针，用来遍历字符串 for (i = 0; i < len; i++) { // 遍历数组 if (k == 0 && res == 0) // 如果字符串的开头是零，就跳过 continue; ans[k++] = res + '0'; // 将数组中的每一位转换为字符，加到字符串中 } ans[k] = '\0'; // 在字符串的末尾加上结束符 if (k == 0) // 如果字符串为空，就返回"0" return "0"; return ans; // 返回字符串}
// 主函数int main() { char num1[100]; // 定义第一个字符串 char num2[100]; // 定义第二个字符串 printf("请输入两个非空字符串：\n"); // 提示输入 scanf("%s%s", num1, num2); // 读取输入 char* res = multiply(num1, num2); // 调用函数，得到结果 printf("它们的乘积是：%s\n", res); // 输出结果 return 0;}
程序测试
为了验证我们的程序是否正确，我们可以用一些测试用例来检验。我们可以
输出两个非空字符串，经由程序计算得出两个非空字符串的乘积
源代码获取
#软件下载通道#
我用夸克网盘分享了「20240101」，点击链接即可保存。打开「夸克APP」，无需下载在线播放视频，畅享原画5倍速，支持电视投屏。
链接：https://pan.quark.cn/s/71c4b0f8f8d1
(链接和提取码建议复制粘贴，手动输入容易出现错误）
| #支持一下#
分享整理，测试发布不易 如果您方便的话可以帮忙点一下↓↓
谢谢大家！
|
下期题目
题目：
动态规划-硬币重量最轻问题
设有n种不同面值的硬币，第i种硬币的币值是Vi(其中V1=1),重量是Wii=1,2，...n且现在购买某种总币值为y的商品，需要用这些硬币付款，如果每种钱币使用的个数不限，那么如何选择付款的方法使得付出钱币的总重量最轻?使用动态规划设计策略设计一个求解该问题的算法假设问题的输入实例是:
V1=1，V2=4，V3=6，V4=8W1=1，W2=2，W3=4，W4=6
Y=12
要求输出优化函数表和标记函数表、以及硬币支付方式
点赞加关注，学习不迷路
微信公众号｜工控小新
EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中
发现“分享”和“赞”了吗，戳我看看吧
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
