机试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 条评论
你写得非常清晰明了,让我很容易理解你的观点。