机试Day1

开始写笔记了!此专栏记录机试算法题目的解题过程思路,为机试做准备!!!:smile:

反序数

反序数_牛客题霸_牛客网 (nowcoder.com)

题目:

设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);
}

百鸡问题

百鸡问题_牛客题霸_牛客网 (nowcoder.com)

描述

用小于等于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");
        }   
    }
}
最后修改:2023 年 05 月 26 日
如果觉得我的文章对你有用,请随意赞赏