关于数论:排版CI-叠筐数论CJ-互质查找CK-赌徒基础上机试题

28次阅读

共计 4402 个字符,预计需要花费 12 分钟才能阅读完成。

CI 叠筐

把一个个大小差一圈的筐叠下来,使得从上往下看时,边筐花色交织。这个工作当初要让计算机来实现,得看你的了。

输出
输出是一个个的三元组,别离是,外筐尺寸 n(n 为满足 0 <n<80 的奇整数),核心花色字符,外筐花色字符,后二者都为 ASCII 可见字符;

输入
输入叠在一起的筐图案,核心花色与外筐花色字符从内层起交织相叠,多筐相叠时,最外筐的角总是被打磨掉。叠筐与叠筐之间应有一行距离。

样例输出
5 ^ !
7 ()
0
样例输入(图形显示谬误,应为突围状仿圆形筐形,花纹由内而外按层交织散布)
^^^
^!!!^
^!^!^
^!!!^
^^^

)))))
)((((()
)()))()
)()()()
)()))()
)((((()
)))))

//#include<iostream>
//#include<algorithm>
//#include<cstring>
//#include<cmath>
//using namespace std;
///*
// 用一个缓存数组示意要输入的字符序列。阵列的左上角为(1,1),右下角为(n,n)。由内到外实现排版。// 最内层的横坐标是(n+1)/2
// 而后向上遍历 到 1 为止
// 记 k 为以后地位的横坐标 那么每一行须要打印的字符个数为从 k 到 n-k+1
//*/
//int main(){
//    int n = 0;
//    int a[81][81];
//    char cen,out,cc; //cen:核心字符 out: 外围字符,cc: 暂存备用字符 
//    while(scanf("%d %c %c",&n,&cen,&out)!=EOF){//        if(n == 0){
//            break;
//        } 
//        int k = (n + 1) / 2;// 找到最核心的地位 
//        int count = 0;// 计数用,偶数用 cen(核心字符)填充(从 count 从 0 开始),奇数用外围 out 填充 
//        for(int i = k; i >= 1; i--){// 横纵坐标均从 1 开始 
//            if(count % 2 == 0){// 用 count 奇偶来判断填充哪个字符 
//                cc = cen; 
//            }else{
//                cc = out;
//            }
//            for(int j = i; j <= n - i + 1 ; j++){//n - i + 1 为与 i 对称地位的坐标 
//                a[i][j] = a[n - i + 1][j] = cc; // 随 j 的变动横向→纵列↓填充
//                a[j][i] = a[j][n - i + 1] = cc; // 随 j 的变动纵向↓横列→填充 
//            }
//            count++;// 计数器记录 
//        }
//        if(n != 1){// 不是只有一个筐的状况下,每个角都要被赋值为空格 ' ' 
//            a[1][1] = a[1][n] = a[n][1] = a[n][n] = ' ';// 四个角置空格    
//        }
//        for(int i = 1; i <= n; i++){//            for(int j = 1; j <= n; j++){//                printf("%c",a[i][j]);
//            }
//            printf("\n");
//        }
//        printf("\n");
//    }
//    return 0;
//}

CJ 互质

给你一个正整数 n,请问有多少个比 n 小的且与 n 互质的正整数?
两个整数互质的意思是,这两个整数没有比 1 大的公约数。
输出
输出蕴含多组测试数据。每组输出是一个正整数 n(n<=1000000000)。当 n = 0 时,输出完结。
输入
对于每组输出,输入比 n 小的且与 n 互质的正整数个数。
样例输出 Copy
7
12
0
样例输入 Copy
6
4

欧拉函数参考自 https://www.cnblogs.com/hands…

//#include<iostream>
//#include<algorithm>
//#include<cstring>
//#include<cmath>
//using namespace std;
////typedef long long ll;// 能够用 typedef 将 long long 名称化简为 ll 
///*
// 质数 = 素数
//φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中 p(1),p(2)…p(n)为 x 的所有质因数 
// 两个整数互质的意思是,这两个整数没有比 1 大的公约数(两个数不用为质数)// 质因数,就是指一个正整数的约数,且必须为质数,也称质因子或质约数,如 30 的质因数为 2,3,5,没 6
//*/
//long long Euler(long long x){
//    long long res = x;// 给 res 赋初值 x, 便于前面连乘 
//    for(long long i = 2; i*i <= x; i++){// 不必对 2 - x 全副取余,只需对 2 - 根号 x 取余 
//        if(x % i == 0){// i 为一个质因子 
//            res = res / i *(i - 1);// 先进行除法避免溢出(ret=ret*(1-1/p(i)))
//            while(x % i == 0){// 留神此处 x 仍为传入的数值,并未变动,变动的是 res 
//                x /= i; // 将失去的质因子从 x 中除去, 如若 30 不除去 2 这个质因数,则 30 % 6 == 0,6 这个不是其质因数的数也会被计算在 res 内) 
//            }    
//        }
//    }
//    if(x > 1){// 保障咱们曾经除完了 n 的所有的质因子,若 n > 1 有可能还会呈现一个咱们未除的因子
//        res = res / x * (x - 1);// 剩下一个未除去的质因子是 x 本身,即 1 -1/x = (x - 1)/x 
//    }
//    return res;
//}
//int main(){
//    long long n = 0;
//    while(scanf("%lld",&n)!=EOF,n){//        printf("%lld\n",Euler(n));
//    }
//    return 0;
//}

CK 赌徒

有 n 个赌徒打算赌一局。规定是:
每人下一个赌注,赌注为非负整数,且任意两个赌注都不雷同。胜者为赌注恰好是其余任意三个人的赌注之和的那个人。如果有多个胜者,咱们取赌注最大的那个为最终胜者。
例如,A,B,C,D,E 别离下赌注为 2、3、5、7、12,最终胜者是 E,因为 12=2+3+7。
输出
输出蕴含多组测试数据。每组首先输出一个整数 n(1<=n<=1000),示意赌徒的个数。
接下来 n 行每行输出一个非负整数 b(0<=b<32768),示意每个赌徒下的赌注。
当 n = 0 时,输出完结。
输入
对于每组输出,输入最终胜者的赌注,如果没有胜者,则输入 no solution。
样例输出 Copy
5
2
3
5
7
12
5
2
16
64
256
1024
0
样例输入 Copy
12
no solution

这个题的测点很迷,根本很水的或者谬误的都能通过,上面写一下暴力枚举和二分的做法,尽量把二分当做主解决方案!

//#include<iostream>
//#include<algorithm>
//#include<cstring>
//#include<cmath>
//using namespace std;
///*
// 本题暴力 + 枚举 
// 三重循环 a[i], a[j], a[k],a[l]别离代表四个人先选一个以后最大的值 a[i];
// 而后找一个第二大的 a[j]用 a[i]减去 a[j]和 a[k]失去差 a[l];
// 如果在剩下的数据中找到 a[l]就阐明这四个人是合乎题中形容的条件的;
// 对于 a【i】,找过的就不必再找了,因为我是从大往小找的
// 所以找到的第一个就是赌注最大的那个,之后完结循环输入就能够了。//*/
//int main(){
//    int n = 0,i,j,k,l;
//    int a[1001];
//    while(scanf("%d",&n) != EOF,n){
//        int flag = 0;// 标记是否找出了胜者 
//        for(i = 0; i < n; i++){//            scanf("%d",&a[i]);
//        }
//        sort(a,a + n);// 把筹码升序排列 
//        for(i = n - 1; i >= 3; i--){//            for(j = i - 1; j >= 2; j--){//                for(k = j - 1; k >= 1; k--){//                    for(l = k - 1; l >= 0; l--){//                        if(a[i] - a[j] - a[k] == a[l]){//                            printf("%d\n",a[i]);
//                            flag = 1;
//                            break;//
//                        }
//                    }
//                    if(flag){
//                        break;
//                    }
//                }
//                if(flag){
//                    break;
//                } 
//            }
//            if(flag){
//                break;
//            }
//        }
//        if(!flag){//            printf("no solution\n");
//        }    
//    }
//    return 0;
//}
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
/*
第二种:暴力 + 二分枚举 
 三重循环 a[i], a[j], a[k],a[l]别离代表四个人先选一个以后最大的值 a[i];
 而后找一个第二大的 a[j]用 a[i]减去 a[j]和 a[k]失去差 a[l];
 如果在剩下的数据中找到 a[l]就阐明这四个人是合乎题中形容的条件的;
 对于 a【i】,找过的就不必再找了,因为我是从大往小找的
 所以找到的第一个就是赌注最大的那个,之后完结循环输入就能够了。*/
// 二分查找
int Binary_Search(int a[],int low,int high,int key){ 
    int mid;
    while(low <= high){mid = (low + high) / 2;
        //>> 是能够看做是除 2,如 12 的二进制 zhi 示意是 00001100,>>1 将 00001100 右移一位,变为 00000110,即 6
        if(key == a[mid]){return mid;}else if(key < a[mid]){high = mid - 1;}else{low = mid + 1;}
    }
    return -1;
} 
int main(){
    int n = 0,i,j,k,p,bet,ans;
    int a[1001];
    while(scanf("%d",&n) != EOF,n){
        int flag = 0;// 标记是否找出了胜者 
        for(i = 0; i < n; i++){scanf("%d",&a[i]);
        }
        sort(a,a + n);// 把筹码升序排列 
        for(i = n - 1; i >= 0; i--){for(j = 0; j < i; j++){for(k = j + 1; k < n; k++){bet = a[i] - a[j] - a[k];
                    p = Binary_Search(a,k + 1,n,bet);//j = 0,k = j + 1 = 1,二分查找的地位是 a[k]之后的地位 k + 1 开始始终到 n 
                    if(p != -1 && p !=i){//p!= i 是避免其余值均为 0,找到其自身(a[i]-0-0 = a[i])与自身雷同 
                        ans = i;
                        flag = 1;// 查找胜利, 置 1 
                        break;
                    }
                }
                if(flag){break;} 
            }
            if(flag){break;}
        }
        if(!flag){printf("no solution\n");
        }else{printf("%d\n",a[ans]);
        }    
    }
    return 0;
}

正文完
 0