廣西大學2020級計算機系題庫代碼決議與參考答案
文章目錄
- 前言
- 一、判斷升序
- 極簡版
- 標準版
- 二、小西的排序
- 極簡版（快速排序）
- 標準版（冒泡排序）
- 三、小西的數(動詞)數(名詞)
- 暴力思維極簡
- 純思維高效解
- 四、小西買西瓜
- 標準代碼，動態規劃思想
- 極簡版數學代碼
- 五、通話記錄
- 標準代碼
- 極簡代碼（神仙優化）
- 六、基礎練習 字串對比
- 標準代碼實作
- 七、排列問題
- 標準代碼
- 簡易版搜索
- 八、組合問題
- 標準代碼實作
- 九、小西與資料結構
- 標準代碼
- 十、進制轉換
- 標準代碼
前言
提示：代碼分為極簡版本和標準化版本，并不是說極簡會好背或者標準化版本就繁瑣，各有各的優勢，貼兩副代碼僅供各位參考學習，預祝各位程設考出好成績
一、判斷升序
主要思路是前者與后者相比大小，符合條件即輸出YES^NO；
極簡版
#include<stdio.h>
int x[200005] = {},i=1,flag=1;
int main()
{
scanf("%d", &x[0]);
while (scanf("%d", &x[i]) != EOF) (x[i - 1] <= x[i])?i++:(flag=0);
flag?printf("YES"):printf("NO");
}//極簡版本
#include<stdio.h>
int x,n=1,f=1;
int main(){
for(f=1,scanf("%d",&x);~scanf("%d",&n);x=n) f&=x<=n;
puts(f?"YES":"NO");
}
標準版
#include<stdio.h>
int main(void)
{
long long a[50004] = {};
int i = 1;
int flag = 0;
a[0] = -0x3f3f3f3f;//最小值
while (scanf("%d", &a[i])!=EOF) {
if (a[i] >= a[i - 1]){//這一步是用來和前一項比較
i++;
}
else flag = 1;
}
if(flag)
printf("NO\n");
else printf("YES\n");
return 0;
}//工業化代碼
二、小西的排序
主要思路是利用結構體去捆綁排序，排序的有效手段是快速排序和冒泡排序；
極簡版（快速排序）
代碼如下（示例）：
#include<stdio.h>
#include<stdlib.h>
typedef struct node {char x[20];double y;}T;
T x[2005] = {};
//快速排序的多載函式，用于比較大小
int cmp(const void* a, const void* b)
{
return (*(T*)a).y > (*(T*)b).y ;
}
int main()
{
int n;
while (scanf("%d", &n) != EOF) {
for (int i = 0; i < n; i++) scanf("%s %lf", &x[i].x, &x[i].y);
qsort(x, n, sizeof(T), cmp);//快速排序，直接多載裝上就排好了
for (int i = 0; i < n; i++) printf("%s ", x[i].x);
printf("\n");
}
}
標準版（冒泡排序）
代碼如下（示例）：
#include<stdio.h>
int n;
struct {char s[21];double hi;}bd[100],t;
int main(){
while(~scanf("%d",&n)){
for(int i=0;i<n;i++) scanf("%s %lf",&bd[i].s,&bd[i].hi);
for(int i=0;i<n;i++) for(int j=1;j<n;j++)
if(bd[j].hi<bd[j-1].hi) t=bd[j-1],bd[j-1]=bd[j],bd[j]=t;
for(int i=0;i<n;i++) printf("%s ",bd[i].s);
puts("");
}
}
三、小西的數(動詞)數(名詞)
就每個位的數字都統計一遍得了，資料不大，肯定能過，
暴力思維極簡
#include<stdio.h>
#define ll long long
ll ans = 0,n,flag;
int x[2005] = {};
int main()
{
while (scanf("%d%d", &n,&flag)!=EOF ){
ans = 0;
for (int i = 1; i <= n; i++) {
int tmp = i;
while (tmp) {
if (tmp%10 == flag) ans++;
tmp /= 10;
}
}
printf("%lld\n", ans);
}
}
純思維高效解
不建議在考試的時候使用本代碼，思維挺大的
#include<stdio.h>
int main(){
int n,x,m=1,ans=0;
while(scanf("%d%d",&n,&x)!=EOF){
ans=0,m=1;
while(m<=n){
int a=n/(m*10),b=n/m%10,c=n%m; //a,b,c為n的三部分，求哪一位x的個數，b就為那一位數，a為b左邊的數，c為b右邊的數，如求1~728中十位7的個數，則a=7，b=2，c=8
if(x){
if(b>x) ans+=(a+1)*m; //如果b>x，說明有(a+1)*m個x（如求1~728中個位7的個數，則為（72+1）*1=73）
if(b==x) ans+=a*m+c+1; //如果b=x，說明有a*m+c+1個x（如求1~728中百位7的個數，則為0*100+28+1=29）
if(b<x) ans+=a*m; //如果b<x，說明有a*m個x（如求1~728中十位7的個數，則為7*10個）
}
else{ //x=0的情況和x！=0的情況有所不同
if(b) ans+=a*m;
else ans+=(a-1)*m+c+1;
}
m*=10;
}
printf("%d\n",ans);
}
}
四、小西買西瓜
主體思路就是能買五就買5，不行就買3，輸出即可，
其他思路主要是動態規劃思想，利用前面的結果去影響后面的行程，不推薦考試使用
標準代碼，動態規劃思想
#include<string.h>
#include<stdlib.h>
#define ll long long
#define max(a,b) a>b?a:b;
ll ans = 0;
int x[2005] = {};
int main()
{
int n;
int flag;
while (scanf("%d", &n) != EOF) {
ans = 0;
int dp[10000] = {};
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
dp[4] = 5;
for (int i = 5; i <= n; i++) {
dp[i] = max(dp[i - 3] + 4, dp[i - 5] + 7);
}
printf("%d\n", dp[n]);
}
}
極簡版數學代碼
#include<stdio.h>
int main(void)
{
long long int a,sum;
while(scanf("%lld",&a)!=EOF){
sum=a+a/5*2+a%5/3;
printf("%lld\n",sum);
}return 0;
}
五、通話記錄
代碼的主要思想還是資料結構的堆疊，存進去，然后存出來，只不過是利用了陣列進行了簡單的模擬標準代碼
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define ll long long
#define max(a,b) a>b?a:b;
ll ans = 0;
typedef struct x {
int a;
ll b;
} T;
T x[2005] = {};
ll z[5][2000] = {0};
int main()
{
int n;
int flag=10;
int i = 0;
int j = 0, k = 0, l = 0;
while (scanf("%d%lld", &x[i].a,&x[i].b) != EOF) {
if(x[i].a==0)
z[x[i].a][j++] = x[i].b;
else if (x[i].a == 1)
z[x[i].a][k++] = x[i].b;
else if (x[i].a == 2)
z[x[i].a][l++] = x[i].b;
}
while (flag--) {
--j >= 0 ? printf("%lld ", z[0][j]) :printf("0 ") ;
--k >= 0 ? printf("%lld ", z[1][k]) : printf("0 ");
--l >= 0 ? printf("%lld", z[2][l]) : printf("0");
printf("\n");
}
}
極簡代碼（神仙優化）
#include<stdio.h>
long long s[3][10]={},q[3]={},i;
int main(){
while(~scanf("%lld",&i))
scanf("%lld",&s[i][q[i]++%10]);//mod10只取前十個資料，遵守先進后出原則
for(int i=0;i<10;i++)
for(int j=0;j<3;j++)
printf("%lld",s[j][(--q[j]+20)%10]),//模擬堆疊出，20用來保護陣列不會爆
putchar(j==2?'\n':' ');//細節上一句是，因此下一句在緊跟上一句直接執行，判定是否空格或回車
}
六、基礎練習 字串對比
其實挺短的了，就先貼出來給大家做一個參考，有疑問可以下面評論，標準代碼實作
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define ll long long
ll ans = 2;
char x[1000] = {};
char y[1000] = {};
int main()
{
scanf("%s%s", &x, &y);
ll a, b = 0;
a = strlen(x);
b = strlen(y);
if (a == b) {
for (int i = 0; i < a; i++) {
if (x[i] != y[i]) {
if (x[i] == y[i] - 'A' + 'a' || x[i] - 'A' + 'a' == y[i]) ans = 3;
else {
ans = 4;
break;
}
}
}
}
else ans = 1;
printf("%lld", ans);
}
七、排列問題
廢話也不多說，標準版的代碼注釋詳盡，基本上也可以看懂了標準代碼
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
int N, K, count=0, key=1;
int a[10][10] = {}, num[10] = {};
//cmp是經典的qsort多載部分，用于定義排序的比較內容 ，比較效果，這里定義的是從小到大排序
int cmp(const void* a, const void* b) {
return(*(int*)a > * (int*)b);
}
//dfs，同樣是全排列
void arrange(int r)
{
//出現了第count個排列，那么count++，也就是有一組排列排好了
if (r == N) {
count++;
}
//如果這組排列滿足了第k組，那么就把他輸出
if (count == K) {
for (int i = 0; i < N; i++) {
printf("%d ", num[i]);
}
printf("\n");
key = 0;//宣布陣列輸出結束
}
//全排列本體，可以用手模擬自己排列的程序來推導
for (int i = r; i < N; i++) {
//將后面的n-r個數字進行從小到大排序，實作從小到大全排列
qsort(num + r, N - r, sizeof(int), cmp);
int t;
t = num[i];
num[i] = num[r];
num[r] = t;//新的最小值放最前面，原來的最小值和新值交換位置
if (r == 0) arrange(r + 1);//判定條件，然后dfs
else if( a[num[r - 1]][num[r]] != 0) arrange(r + 1);
if (key == 0) return;//發現結束了，那就結束了
}
}
int main()
{
scanf("%d%d", &N, &K);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) scanf("%d", &a[i][j]);//收集矩陣條件
num[i] = i;//初始化陣列
}
arrange(0);
return 0;
}
簡易版搜索
#include<stdio.h>
int vis[12],fob[12];
int stir[12][12],ans[12];
int n,k,ki=0;
void print(){
for(int i=0;i<n;i++) printf("%d%c",ans[i],i==n-1?'\n':' ');
}
void dfs(int len){
if(len==n) {
ki++;
if(ki==k) print();
}
for(int i=0;i<n;i++)
if(vis[i]==0){
if(len>0&&stir[ans[len-1]][i]==0) continue;
ans[len]=i;
vis[i]=1;
dfs(len+1);
vis[i]=0;
}
}
int main() {
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&stir[i][j]);
dfs(0);
}
八、組合問題
畫圖理解組合到底如何進行，利用遞回完成若干個回圈的深入，標準代碼實作
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
long long n, r, arr[50000] = {};
void func(long long step, long long t) {
if (step == r + 1)
{
for (int j = 1; j <= r; j++)
printf("%lld" , arr[j]);
printf("\n");
return;
}
for (long long i = t + 1; i <= n - r + step; i++)
{
arr[step] = i;
func(step + 1, i);
}
return;
}
int main()
{
long long k;
scanf("%lld", &k);
while (k--)
{
scanf("%lld %lld", &n, &r);
func(1, 0);
}
return 0;
}
九、小西與資料結構
這題我考慮直接進行資料模擬，代碼也挺清晰好懂，標準代碼
#include<stdio.h>
int main()
{
int m,n,t,i,j,x;
long long int s[50000]={},a,b,c,sum=0;
while(scanf("%d%d",&n,&m)!=EOF){
i=1;
while(n--){
scanf("%lld",&s[i]);
i++;
}
for(j=0;j<m;j++){
scanf("%d",&t);
if(t==1){
scanf("%lld%lld",&a,&b);
for(int tmp=a;tmp<=b;tmp++){
sum+=s[tmp];
}
printf("%lld\n",sum);
sum=0;
}
else if(t==2){
scanf("%lld%lld%lld",&a,&b,&c);
for(x=a;x<=b;x++){
s[x]+=c;
}
}
}
}
return 0;
}
十、進制轉換
這題的核心是如何裝下一個巨大的數字，我的思路是直接全部讀成字串，通過模擬的方式把字串當成數字進行進制轉換，標準代碼
#include<stdio.h>
#include<string.h>
int main()
{
char a[1000],a1[1000];
long b;
int i, j, n, mod, mod1;
while (scanf("%s", a)!=EOF)
{
n = strlen(a);
b = 0;
i = 0;
while (i != n)
{
mod = 0;
mod1 = 0;
a1[b++] = (a[n - 1] - '0') % 2 + '0';
for (j = i; j < n; j++)
{
mod = (mod1 * 10 + a[j] - '0') % 2; //余數
a[j] = (mod1 * 10 + a[j] - '0') / 2 + '0'; //商
mod1 = mod; //余數
}
if (a[i] == '0')
i++;
}
for (b--; b >= 0; b--)
{
printf("%c", a1[b]);
}
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245674.html
標籤：其他
上一篇：計算機網路復習題（僅供參考）