本文主要是介绍天平称重问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
天平称重问题:
用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码,重量分别是1,3,9,27,81
则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。
本题目要求编程实现:对用户给定的重量,给出砝码组合方案。
例如:
用户输入:
5
程序输出:
9-3-1
用户输入:
19
程序输出:
27-9+1
要求程序输出的组合总是大数在前小数在后。
可以假设用户的输入的数字符合范围1~121。
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
char* reve(char *s) //用于“+”“-”号转换
{int n = strlen(s);for (int i = 0; i < n;i++){if (s[i]=='-'){s[i] = '+';}else if (s[i]=='+'){s[i] = '-';}}char *p = (char *)malloc(n + 2);memset(p, 0, n + 2);p[0] = '-';strcat(p, s);return p;
}
//1:1
//2:3-1
//3:3
//4:3+1
//5:9-3-1
//。。。
char* f(int x)
{char *p = (char *)malloc(1024);memset(p, 0, 1024);//找规律,当X大于(3的n次方的二分之一)时,需要做减法;当x小于(3的n次方的二分之一)时,做加法。int a = 1;while (a < x) a *= 3;if (a == x){_itoa(a, p, 10);return p;}if (x <= a / 2){int m = x - a / 3;char *p1 = f(m);_itoa(a/3, p, 10);strcat(p, "+");return strcat(p, p1);}char *h = reve(f(a - x));_itoa(a, p, 10);strcat(p, h);return p;
}void main(){for (int i = 1; i < 100; i++){char*p=f(i);printf("%d : %s\n", i, p);}
}
方法2
余数代表增加或减少,以19和22为例
#include<stdio.h>
#include<stdlib.h>
#include<string.h>char * f2(int n){char*p = (char*)malloc(1024);memset(p, 0, 1024);int q = 1; //表示权重while (n > 0){int sh = n / 3; //表示商并进行保存if (n % 3 == 1) //等于1表示要加上{char arr[1024] = { 0 };strcpy(arr, p);memset(p, 0, 1024);strcat(p, "+");char arr1[1024] = { 0 };_itoa(q, arr1, 10);strcat(p, arr1);strcat(p, arr);}if (n % 3 == 2) //等于2表示要减去{sh++; //让他的下一位满足除3的条件,就是将最大的权重补上eg:27char arr[1024] = { 0 };strcpy(arr, p);memset(p, 0, 1024);strcat(p, "-");char arr1[1024] = { 0 };_itoa(q, arr1, 10);strcat(p, arr1);strcat(p, arr);}n = sh; //商进行更新q *= 3; //将权重更新}return p+1;
}void main(){for (int i = 1; i < 100; i++){char*p = f2(i);printf("%d : %s\n", i, p);}
}
这篇关于天平称重问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!