机试Day1
开始写笔记了！此专栏记录机试算法题目的解题过程思路，为机试做准备！！！:smile:
反序数
题目：
设N是一个四位数，它的9倍恰好是其反序数（例如：1234的反序数是4321）
求N的值
输入描述：
程序无任何输入数据。
输出描述：
输出题目要求的四位数，如果结果有多组，则每组结果之间以回车隔开。答案只有1089
思路：
基本就是暴力破解，关键看怎么减少次数
法1：函数求反序数（参考答案给的）
#include <cstdio>
#include <iostream>
using namespace std;
int Reverse(int x){
int revx = 0;
while (x != 0) {
revx *= 10;
revx += x % 10;
x /= 10;
}
return revx;
}
int main(){
for (int i = 1000; 9 * i <= 9999; ++i) {
if (i * 9 == Reverse(i)) {
printf("%d\n", i);
}
}
}法2：根据反序数每位数字比较
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
for (int i = 1000; i * 9 < 10000; i++) {
if (i % 10 == 9 * i / 1000 && i % 100 / 10 == 9 * i / 100 % 10 && i % 1000 / 100 == 9 * i / 10 % 10 && i / 1000 == 9 * i % 10){
printf("%d\n", i);
}
}
}这种方法比较两个数，假设原来数为a=i，则反序数为b=9*i：a的个位等于b的千位，a的十位等于b的百位，以此类推，进行比较
为了减少比较次数，b一定小于10000，即i的九倍小于10000，可以缩小范围
法3：分别遍历原来数的千、百、十、个位
分析可得：原来数千位一定为1，个位一定为9（因为9倍的数千位为9），只需遍历原来数的百位和十位
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
int a = 1, d = 9;
for (int b = 0; b <= 9; ++b) {
for (int c = 0; c <= 9; ++c) {
if ((1000 * a + 100 * b + 10 * c + d) * 9 == 1000 * d + 100 * c + 10 * b + a) {
printf("%d\n", 1000 * a + 100 * b + 10 * c + d);
}
}
}
}对称平方数1
对称平方数1_牛客题霸_牛客网 (nowcoder.com)
描述：
打印所有不超过256，其平方具有对称性质的数。如2，11就是这样的数，因为2*2=4，11*11=121。
输入描述：
无任何输入数据
输出描述：
输出具有题目要求的性质的数。如果输出数据不止一组，各组数据之间以回车隔开。
思路：最好的方法就是上题求反序数的函数，比较即可；或者用c++的string库将数字转为字符串，比较对称位
法1：求反序数
#include <iostream>
using namespace std;
int Reverse(int x){
int revx = 0;
while (x != 0) {
revx *= 10;
revx += x % 10;
x /= 10;
}
return revx;
}
int main() {
int s, t;
for (int i = 0; i <= 256; i++) {
if (i * i == Reverse(i * i)) {
printf("%d\n", i);
}
}
}法2：<string>
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
bool check(int n){
string s;
s = to_string(n);
int len = s.length();
for(int i = 0; i < len / 2; i++){
if(s[i] != s[len - i - 1]){
return false;
}
}
return true;
}
int main(){
for(int i = 0; i <= 256; i++){
if(check(i * i)){
printf("%d\n", i);
}
}
return 0;
}与7无关的数
与7无关的数_牛客题霸_牛客网 (nowcoder.com)
描述
一个正整数,如果它能被7整除,或者它的十进制表示法中某个位数上的数字为7, 则称其为与7相关的数.现求所有小于等于n(n<100)的与7无关的正整数的平方和。
输入描述：
案例可能有多组。对于每个测试案例输入为一行,正整数n,(n<100)
输出描述：
对于每个测试案例输出一行，输出小于等于n的与7无关的正整数的平方和。
思路：由于限定n<100，即只有个位十位，所以直接三个判定条件即可：个位不为7、十位不为7，不是7的倍数
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int output = 0, n = 0;
scanf("%d",&n);
for (int i = 1; i <= n; i++) {
if (i%7!=0 && i%10!=7 && i/10!=7) {
output += i * i;
}
}
printf("%d", output);
}百鸡问题
描述
用小于等于n元去买100只鸡，大鸡5元/只，小鸡3元/只,还有1/3元每只的一种小鸡，分别记为x只,y只,z只。编程求解x,y,z所有可能解。
输入描述：
测试数据有多组，输入n。
输出描述：
对于每组输入,请输出x,y,z所有可行解，按照x，y，z依次增大的顺序输出。
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int n, x, y, z;
scanf("%d", &n);
for (x = 0; x <= 100; x++) {
for (y = 0; y <= 100; y++) {
for (z = 0; z <= 100; z++) {
if (15 * x + 9 * y + z <= n*3 && x + y + z == 100) {
printf("x=%d,y=%d,z=%d\n", x, y, z);
}
}
}
}
}Old Bill
Old Bill_牛客题霸_牛客网 (nowcoder.com)
描述
N只火鸡的价格为$_XYZ_，总数N在1-99，价格五位数，两位看不清。假设第一位不为0，每只火鸡价格为整数，所有火鸡价格相同。编写程序猜测褪色数字和火鸡的原始价格，输出最昂贵的那个
输入描述：
The first line of the input file contains an integer N (0<N<100), which represents the number of turkeys. In the following line, there are the three decimal digits X, Y, and Z., separated by a space, of the original price $_XYZ_.
输出描述：
For each case, output the two faded digits and the maximum price per turkey for the turkeys.
法1：mine，遍历可能的单价
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int n, x, y, z;
while (~scanf("%d\n", &n)) {
scanf("%d %d %d", &x, &y, &z);
int price = 0;
for (int i = (10000 + x * 1000 + y * 100 + z * 10) / n; n * i < 100000; i++) {
if (n * i / 10 % 10 == z && n * i / 100 % 10 == y && n * i / 1000 % 10 == x) {
price = i;
}
}
if (price) {
printf("%d %d %d\n", n * price / 10000, n * price % 10, price);
} else {
printf("0\n");
}
}
}首先最低单价大于等于1万加上已知的三位数，除以N即为最小单价；最大单价为1万除以N。遍历即可
法2：更简洁的方法，设那俩空缺位，但需要更大空间
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int n, x, y, z;
while (~scanf("%d\n", &n)) {
scanf("%d %d %d", &x, &y, &z);
int i0, j0, price = 0;
for (int i = 1; i <= 9; i++){
for (int j = 0; j <= 9; j++){
if(((i * 10000 + x * 1000 + y * 100 + z * 10 + j) / n) * n == i * 10000 + x * 1000 + y * 100 + z * 10 + j){
i0 = i;
j0 = j;
price = (i * 10000 + x * 1000 + y * 100 + z * 10 + j) / n;
}
}
}
if (price) {
printf("%d %d %d\n", i0, j0, price);
} else {
printf("0\n");
}
}
}
1 条评论
你写得非常清晰明了，让我很容易理解你的观点。