时间:2021年4月12日17:21:04
注:简单的自己做,复杂的参考别人的
1、链表:取得倒数第n个数
#include <stdio.h>
#include <stdlib.h>
struct ListNode{
int m_nKey;
struct ListNode* m_pNext;
};
#define NEW_NODE ((struct ListNode*)malloc(sizeof(struct ListNode)))
#define NULL_THEN_RETURN_VOID do{if(head == NULL)return;}while(0);
#define NULL_THEN_RETURN(x) do{if(head == NULL)return x;}while(0);
struct ListNode *que_init(void)
{
struct ListNode* head = NEW_NODE;
head->m_pNext = NULL;
return head;
}
void que_in(struct ListNode* head, int key)
{
NULL_THEN_RETURN_VOID;
struct ListNode * prob = head;
while(prob->m_pNext != NULL)
{
prob = prob->m_pNext;
}
prob->m_pNext = NEW_NODE;
prob->m_pNext->m_nKey = key;
prob->m_pNext->m_pNext = NULL;
}
int que_totle(struct ListNode* head)
{
NULL_THEN_RETURN(-1);
int cnt = 0;
struct ListNode * prob = head->m_pNext;
while(prob != NULL)
{
cnt++;
prob = prob->m_pNext;
}
return cnt;
}
struct ListNode *que_getkey(struct ListNode* head, int n)
{
NULL_THEN_RETURN(NULL);
int totle = que_totle(head);
int cnt = 0;
struct ListNode * prob = head->m_pNext;
while(prob != NULL)
{
//printf("%d ", prob->m_nKey);
cnt++;
if(cnt >= totle - n + 1)
return prob;
prob = prob->m_pNext;
}
return NULL;
}
int main(void)
{
int num, i, key, pos;
while(scanf("%d", &num) != EOF)
{
struct ListNode *head = que_init();
for(i = 0; i < num; i ++)
{
scanf("%d ", &key);
que_in(head, key);
}
scanf("\n");
scanf("%d", &pos);
struct ListNode *node = que_getkey(head, pos);
if(node != NULL)
{
printf("%d\n",node->m_nKey);
}
else
{
printf("0\n");
}
}
return 0;
}
2、最小编辑距离
(未通过)
#include <stdio.h>
#include <string.h>
//让短字符串在前,长字符串在后
char str_buf1[4096] = {0};
char str_buf2[4096] = {0};
char *str1, *str2;
int end_pos1, end_pos2;
int cnt, cnt_tmp;
int str_op(int pos1, int pos2)
{
if(cnt > cnt_tmp)
{
return 0;
}
if(pos2 >= end_pos2)
{
if(cnt < cnt_tmp)
cnt_tmp = cnt;
//printf("OK pos2 cnt=%d\n", cnt);
return 0;
}
if(pos1 >= end_pos1)
{
if(cnt + (end_pos2 - end_pos1) < cnt_tmp)
{
cnt_tmp = cnt + (end_pos2 - end_pos1);
// printf("OK pos1 cnt=%d end_pos1=%d end_pos2=%d\n", cnt_tmp, end_pos1, end_pos2);
return 0;
}
}
else if(str1[pos1] == str2[pos2])
{
str_op(pos1 + 1, pos2 + 1);
}
else //插入;替换;删除
{
cnt++;
str_op(pos1, pos2 + 1);
cnt--;
cnt++;
str_op(pos1 + 1, pos2 + 1);
cnt--;
cnt++;
if(end_pos1 >= 1)
{
end_pos1--;
str_op(pos1 + 1, pos2);
end_pos1++;
cnt--;
}
}
return 0;
}
int main(void)
{
while(scanf("%s\n", str_buf1) != EOF)
{
scanf("%s\n", str_buf2);
end_pos1 = strlen(str_buf1);
end_pos2 = strlen(str_buf2);
if(end_pos1 > end_pos2)
{
str1 = str_buf2;
str2 = str_buf1;
end_pos1 ^= end_pos2;
end_pos2 ^= end_pos1;
end_pos1 ^= end_pos2;
}
else
{
str1 = str_buf1;
str2 = str_buf2;
}
/*strcpy(str_buf1, "abcde");
strcpy(str_buf2, "bcdef");
end_pos1 = strlen(str_buf1);
end_pos2 = strlen(str_buf2);
str1 = str_buf1;
str2 = str_buf2;*/
cnt = 0;
cnt_tmp = end_pos2;
str_op(0, 0);
//printf("%s %s ", str1, str2);
printf("%d\n", cnt_tmp);
}
return 0;
}
(动态规划;参考网友;c++)
/*
本题删除,替换,插入代价全是 1
*/
#include<iostream>
#include<string>
using namespace std;
int calStringDistance(string A,string B);
int main()
{
string charA;
string charB;
while(getline(cin,charA)&&getline(cin,charB))
{
cout<<calStringDistance(charA,charB)<<endl;
}
return 0;
}
int calStringDistance(string A,string B)
{
int row=A.size();//字符串A的长度
int col=B.size();//字符串B的长度
int **dp=new int*[row+1];//动态创建一个二维数组
for(int i=0;i<row+1;i++)
{
dp[i]=new int[col+1]();
}
dp[0][0]=0;//这里代价是0,也就是空字符到空字符,不需要任何编辑
for(int i=1;i<row+1;i++)//这里是A的i个字符到B空字符需要i个删除代价
{
dp[i][0]=i;
}
for(int j=1;j<col+1;j++)//这里是A从空字符到B的j个字符共需要j个插入代价
{
dp[0][j]=j;
}
for(int i=1;i<row+1;i++)
{
for(int j=1;j<col+1;j++)
{
if(A[i-1]==B[j-1])
{
dp[i][j]=dp[i-1][j-1];//如果i和j位置字符相同,说明i和j位置的字符不需要编辑。dp[i][j]=dp[i-1][j-1]
}
else
{
dp[i][j]=dp[i-1][j-1]+1;//这里需要一个替换代价
}
dp[i][j]=min(dp[i-1][j]+1,dp[i][j]);
dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
}
}
return dp[row][col];
}
(依葫芦写的)
#include <stdio.h>
#include <string.h>
int main(void)
{
char A[1024] = {0};
char B[1024] = {0};
int a[500][500], i, j, len_a, len_b;
while(scanf("%s\n%s\n", A, B) != EOF)
{
len_a = strlen(A);
len_b = strlen(B);
a[0][0] = 0;
for(i = 0; i <= len_a; i++)
a[i][0] = i;
for(i = 0; i <= len_b; i++)
a[0][i] = i;
for(i = 1; i <= len_a; i++)
{
for(j = 1; j <= len_b; j++)
{
if(A[i - 1] == B[j - 1])
a[i][j] = a[i - 1][j - 1];
else
a[i][j] = a[i - 1][j - 1] + 1;
if(a[i][j] > (a[i - 1][j] + 1))
a[i][j] = a[i - 1][j] + 1;
if(a[i][j] > (a[i][j - 1] + 1))
a[i][j] = a[i][j - 1] + 1;
}
}
printf("%d\n", a[len_a][len_b]);
}
return 0;
}
3、杨辉三角(简单)
(通过;但是耗时比较久)
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int line, i, j, mark, num, pos, a, b, c;
while(scanf("%d", &line) != EOF)
{
num = 2 * line + 3;
int *A = (int *)malloc(num * sizeof(int));
for(i = 0; i < num; i++)
A[i] = 0;
A[2] = 1;
if(line == 1)
{
printf("-1\n");
continue;
}
a = 0; b = 0; pos = -1;
for(i = 2; i <= line; i++)
{
for(j = 2; j <= (2 * i); j++)//第n行视为 2*n +3 个元素,包含左右两个0
{
c = A[j];
A[j] = a + b + c;
a = b;
b = c;
if(i == line && A[j] % 2 == 0 && A[j] != 0)
{
pos = j - 1;
//printf("==>%d\n", A[j]);
break;
}
}
A[2 * i + 1] = 0;
A[2 * i + 2] = 0;
}
printf("%d\n", pos);
free(A);
}
return 0;
}
(参考网友;通过规律来解答)
#include<stdio.h>
int main()
{
int n=0;
while(scanf("%d",&n)!=EOF)
{
if(n%2==1)//奇数行直接输出2
printf("2\n");
else
{
if(n%4==0)
printf("3\n");
else
printf("4\n");
}
}
}
4、计算7 的个数(简单)
#include <stdio.h>
int tenpow(int n)
{
int i, num;
num = 1;
for(i = 0; i < n; i++)
{
num *= 10;
}
return num;
}
int main(void)
{
int i, j;
int num;
int cnt;
while(scanf("%d", &num) != EOF)
{
cnt = 0;
for(i = 6; i <= num; i++)
{
if(i % 7 == 0)
{
cnt++;
continue;
}
for(j = 0; tenpow(j) < i; j++)
{
if((i % tenpow(j + 1)) / tenpow(j) == 7)
{
cnt++;
break;
}
}
}
printf("%d\n", cnt);
}
return 0;
}
5、完全数统计(简单)
#include <stdio.h>
int main(void)
{
int pos, sum, i, j, num, cnt;
while(scanf("%d", &num) != EOF)
{
cnt = 0;
for(i = 2; i < num; i++)
{
pos = i + 1, sum = 0;
for(j = 1; j < pos; j++)
{
if(i % j == 0)
{
sum += j;
if(j * j != i && j != 1)sum += i / j;
pos = i / j;
}
}
if(i == sum)
cnt++;
}
printf("%d\n", cnt);
}
return 0;
}
6、高精度整数相加(中等)
注:没有考虑负数的情况
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void)
{
char A[10000];
char B[10000];
//char out[10000];
int len_a, len_b, len_max, i, plus, sum;
while(scanf("%s\n%s", A, B) != EOF)
{
len_a = strlen(A);
len_b = strlen(B);
len_max = len_a > len_b ? len_a : len_b;
char *out = (char *)malloc((len_max + 1) * sizeof(char));
plus = 0;
for(i = 0; i < len_max; i++)
{
if(len_a - 1 - i < 0)
sum = plus + B[len_b - 1 - i] - '0';
else if(len_b - 1 - i < 0)
sum = plus + A[len_a - 1 - i] - '0';
else
sum = plus + A[len_a - 1 - i] + B[len_b - 1 - i] - (2 * '0');
out[len_max - 1 - i] = sum % 10 + '0';
plus = sum / 10;
}
out[len_max] = '\0';
if(plus == 0)
printf("%s\n", out);
else
printf("1%s\n", out);
free(out);
}
return 0;
}
7、输入n个整数,输出其中最小的k个(排序;简单)
#include <stdio.h>
void sort(int *in, int n, int pos)
{
int i, j;
for(i = 0; i < pos; i++)
{
for(j = i + 1; j < n; j ++)
{
if(in[i] > in[j])
{
in[i] ^= in[j];
in[j] ^= in[i];
in[i] ^= in[j];
}
}
}
}
int main(void)
{
int i, num, pos;
int in[10000] = {0};
while(scanf("%d%d", &num, &pos) != EOF)
{
for(i = 0; i < num; i++)
scanf("%d ", in + i);
sort(in, num, pos);
for(i = 0; i < pos; i++)
printf("%d ", in[i]);
printf("\n");
}
return 0;
}
8、找字符串第一次只出现一次的字符(简单)
#include <stdio.h>
int main(void)
{
int bit[256] = {0};
char s[10000] = {0};
int i, mark;
while(scanf("%s\n", s) != EOF)
{
for(i = 0; i < 256; i++)
bit[i] = 0;
i = 0;
while(s[i] != '\0')
{
bit[s[i]]++;
i++;
}
mark = 0;
i = 0;
while(s[i] != '\0')
{
if(bit[s[i]] == 1)
{
printf("%c\n", s[i]);
mark = 1;
break;
}
i++;
}
if(mark == 0)
{
printf("-1\n");
}
}
return 0;
}
9、查找偶数的最接近的素数对(简单)
#include <stdio.h>
int isSushu(int num)
{
int i;
for(i = 2; i < (num / i + 1); i++)
{
if(num % i == 0)
return -1;
}
return 0;
}
int main(void)
{
int i, num;
while(scanf("%d", &num) != EOF)
{
for(i = num / 2; i > 1; i --)
{
if(isSushu(i) == 0 && isSushu(num - i) == 0)
{
printf("%d\n%d\n", i, num - i);
break;
}
}
}
return 0;
}
10、放苹果(难)
自己写的;
递归、遍历法;
代码比较“臃肿”;
优点是可以列举所有放法(但这并不是题目所要求的);
//注:最盘子数为100, 放法最大数为10000
#include <stdio.h>
#include <string.h>
struct data_t{
int a[100];
int n;
};
struct data_t data[10000] = {0};
struct data_t data_tmp = {0};
int data_num = 0;
int isEquel(struct data_t d1, struct data_t d2)
{
int i;
if(d1.n != d2.n)
{
return -1;
}
else
{
int bit1[100] = {0};
int bit2[100] = {0};
for(i = 0; i < d1.n; i++)
bit1[d1.a[i]]++;
for(i = 0; i < d2.n; i++)
bit2[d2.a[i]]++;
for(i = 0; i < 100; i++)
if(bit1[i] != bit2[i])
return -1;
}
return 0;
}
void queIn(struct data_t d)
{
int i, mark;
mark = 0;
for(i = 0; i < data_num; i++)
{
if(isEquel(data[i], d) == 0)
{
mark = 1;
break;
}
}
if(mark == 0)
data[data_num++] = d;
}
void queShow(void)
{
int i, j;
printf("=========================start\n");
for(i = 0; i < data_num; i++)
{
for(j = 0; j < data[i].n; j++)
{
printf("%d-", data[i].a[j]);
}
printf("\n");
}
printf("++++++++++++++++++++++++++end\n");
}
int appleCnt(int a, int b)//a:苹果数 b:盘子数 此函数计算a个苹果放置于b个盘子中的放法,其中盘子数固定为b个
{
int i;
if(a < b)//这里一般默认苹果数(a)大于盘子数(b)
{
return 0;
}
if(b <= 2)
{
for(i = 1 ;i <= (a / 2); i++)
{
data_tmp.a[(data_tmp.n)++] = i;
data_tmp.a[(data_tmp.n)++] = a - i;
queIn(data_tmp);
data_tmp.n -= 2;
}
//printf("data_num:%d\n", data_num);
return 0;
}
else
{
for(i = 1; i <= (a - 1); i++)
{
data_tmp.a[(data_tmp.n)++] = i;
//queIn(data_tmp);
appleCnt(a - i, b - 1);
data_tmp.n--;
}
}
return 0;
}
int applePro(int a, int b)
{
int i, totle;
totle = 1;
for(i = 2; i <= b; i++)
{
memset(&data_tmp, 0, sizeof(data_tmp));
memset(data, 0, sizeof(data));
data_num = 0;
appleCnt(a, i);
//queShow();
totle += data_num;
}
return totle;
}
int main(void)
{
int a, b;
while(scanf("%d %d", &a, &b) != EOF)
{
printf("%d\n", applePro(a, b));
}
return 0;
}
参考网友(简洁)
其实这题考的是数学啊,首先当有0个苹果或者是1个盘子的时候,只有一种分法,而其他情况
可以分为两种情况讨论:
1、m<n,则至少有n-m个盘子是空的,此时就相当于将m个苹果分到m个盘子中,此时(m,n)=(m,m)
2、m > n,分法是两种情况分法的和,有一个空盘子和没有空盘子,即(m,n) = (m,n-1)+(m-n,n)
#include <stdio.h>
int fun(int m,int n){
if(m==0||n==1){
return 1;
}else if(m<n){
return fun(m,m);
}else{
return fun(m-n,n)+fun(m,n-1);
}
}
int main(){
int a,b,num;
while(~scanf("%d%d",&a,&b))
printf("%d\n",fun(a,b));
}
11、DNA序列(简单)
#include <stdio.h>
int main(void)
{
int num, pos, i, cnt, cnt_tmp;
char s[10000] = {0};
char buf[10000] = {0};
while(~(scanf("%s\n%d\n", s, &num)))
{
i = num; pos = 0, cnt = 0;
for(i = 0; i < num; i ++)
if(s[i] == 'G' || s[i] == 'C')
cnt++;
cnt_tmp = cnt;
while(s[i] != '\0')
{
if((s[i] == 'G' || s[i] == 'C') &&
(s[i - num] != 'G' && s[i - num] != 'C'))
cnt++;
else if((s[i - num] == 'G' || s[i - num] == 'C') &&
(s[i] != 'G' && s[i] != 'C'))
cnt--;
//printf("i=%d pos=%d cnt=%d pre=%c end=%c\n", i, pos, cnt, s[i - 5], s[i]);
if(cnt_tmp < cnt)
{
cnt_tmp = cnt;
pos = i + 1 - num;
}
i++;
}
for(i = 0; i < num; i ++)
buf[i] = s[pos + i];
buf[num] = '\0';
printf("%s\n", buf);
}
return 0;
}
12、mp3光标(简单)
#include <stdio.h>
int main(void)
{
int num, pos, idx, i, j, size;
char cmd[1000] = {0};
int list[1000] = {0};
while(~(scanf("%d\n%s\n", &num, cmd)))
{
for(j = 0; j < num; j++)
list[j] = j;
idx = 0; pos = 0; i = 0; size = num >= 4 ? 4 : num;
while(cmd[i] != '\0')
{
if(cmd[i] == 'D')
{
idx++;
if(idx >= num)
{
idx = 0;
pos = 0;
}
else if(idx >= pos + size)
{
pos++;
}
}
else if(cmd[i] == 'U')
{
idx--;
if(idx < 0)
{
idx = num - 1;
pos = num - size;
}
else if(idx < pos)
{
pos--;
}
}
i++;
}
// printf("pos=%d idx=%d\n", pos, idx);
for(i = 0; i < size; i ++)
{
printf("%d", list[pos + i] + 1);
if(i != 3)printf(" ");
}
printf("\n%d\n", idx + 1);
}
return 0;
}
13、查找两个字符串中最长的公共子串(中等)
#include <stdio.h>
#include <string.h>
int isOk(char *s1, char *s2, int pos)
{
int i, j, mark, len, len_tmp;
i = 0; len_tmp = 0;
//printf("%s %s\n", s1, s2);
while(s2[i] != '\0')
{
mark = 0; len = 0;
for(j = 0; j < strlen(s1) - pos ; j++)
{
if(s1[pos + j] != s2[i + j])
break;
len++;
}
//printf("i=%d len=%d\n", i, len);
if(len_tmp < len)
len_tmp = len;
i++;
}
return len_tmp;
}
int main(void)
{
char s1[1000] = {0};
char s2[1000] = {0};
char out[1000] = {0};
char *small, *big, *tmp;
int i, j, len_short, len_tmp, pos_tmp, len_xx;
while(~(scanf("%s\n%s\n", s1, s2)))
{
small = s1; big = s2;
len_short = strlen(s1);
if(len_short > strlen(s2) )
{
len_short = strlen(s2);
tmp = small;
small = big;
big = tmp;
}
len_tmp = 0;
pos_tmp = 0;
for(i = 0; i < len_short; i++)
{
len_xx = isOk(small, big, i);
if(len_xx > len_tmp)
{
len_tmp = len_xx;
pos_tmp = i;
}
}
//printf("pos:%d len:%d\n", pos_tmp, len_tmp);
for(i = 0; i < len_tmp; i++)
out[i] = small[pos_tmp + i];
out[len_tmp] = '\0';
printf("%s\n", out);
}
return 0;
}
14、配置文件恢复(一般难度)
#include <stdio.h>
#include <string.h>
struct cmd_t{
char str[2][64];
char info[64];
int n;
};
//6条命令
#define CMD_NUM 6
struct cmd_t cmd_info[]={
{{"reset", "xx"}, "reset what", 1},
{{"reset", "board"}, "board fault", 2},
{{"board", "add"}, "where to add", 2},
{{"board", "delete"}, "no board at all", 2},
{{"reboot", "backplane"}, "impossible", 2},
{{"backplane", "abort"}, "install first", 2}
};
struct cmd_t cmd_error = {{"he", "he"}, "unknown command", 2};
int isMatch(struct cmd_t cm)
{
int i, j, mark, cnt, idx;
cnt = 0;
for(i = 0; i < CMD_NUM; i++)
{
if(cm.n == cmd_info[i].n)
{
mark = 1;
for(j = 0; j < cm.n; j++)
{
if(strncmp(cm.str[j], cmd_info[i].str[j], strlen(cm.str[j])) != 0)
{
mark = 0;
break;
}
}
if(mark == 1)
{
cnt++;
if(cnt == 1)
idx = i;
else if(cnt >= 2)
break;
}
}
}
if(cnt == 1)
return idx;
return -1;
}
int cmdPro(char *str)
{
//printf("=====>[PRO]%s\n", str);
int pos, i, mark, ret;
struct cmd_t cm = {0};
i = 0; mark = 0;
while(str[i] != '\0')
{
if(str[i] == ' ')
{
pos = i;
mark = 1;
break;
}
i++;
}
if(mark == 1)
{
strcpy(cm.str[0], str);
cm.str[0][pos] = '\0';
strcpy(cm.str[1], str + pos + 1);
cm.n = 2;
}
else
{
strcpy(cm.str[0], str);
cm.n = 1;
}
ret = isMatch(cm);
if(ret == -1)
printf("%s\n", cmd_error.info);
else
printf("%s\n", cmd_info[ret].info);
return 0;
}
int main(void)
{
char s[128] = {0};
char cmd1[128] = {0};
char cmd2[128] = {0};
int cnt = 0;
while(gets(s))
{
//printf("-------------------------------------[%d][%s]\n", cnt++, s);
if(strlen(s) > 0)
cmdPro(s);
}
return 0;
}
15 算24(略难)
递归、遍历法
#include <stdio.h>
#define PRO_NUM 4
int mark = 0;
char result_str[][16] = { "false", "true"};
int shuPro(int *p, int n)
{
int i, j, k, tmp_cnt;
int tmp[PRO_NUM] = {0};
if(mark == 1)
{
//printf("OK\n");
return 0;
}
if(n <= 1)
{
if(p[0] == 24)mark = 1;
return 0;
}
else
{
for(i = 0; i < n; i ++)
for(j = 0; j < n; j++)
{
if(i != j)
{
tmp_cnt = 0;
for(k = 0; k < n; k++)
if(k != i && k != j)
tmp[tmp_cnt++] = p[k];
tmp[tmp_cnt] = p[i] + p[j]; //加
shuPro(tmp, n - 1);
tmp[tmp_cnt] = p[i] - p[j]; //减-A
shuPro(tmp, n - 1);
tmp[tmp_cnt] = p[j] - p[i]; //减-B
shuPro(tmp, n - 1);
tmp[tmp_cnt] = p[i] * p[j]; //乘
shuPro(tmp, n - 1);
if(p[j] != 0 && p[i] % p[j] == 0 )
{
tmp[tmp_cnt] = p[i] / p[j]; //除A
shuPro(tmp, n - 1);
}
if(p[i] != 0 && p[j] % p[i] == 0 )
{
tmp[tmp_cnt] = p[j] / p[i]; //除B
shuPro(tmp, n - 1);
}
}
}
}
return 0;
}
int main(void)
{
int shu[PRO_NUM] = {0};
while(~(scanf("%d %d %d %d\n", shu, shu + 1, shu + 2, shu + 3)))
{
mark = 0;
shuPro(shu, 4);
printf("%s\n", result_str[mark]);
}
return 0;
}
网友参考:dfs --- 深度优先算法
#include <stdio.h>
#include <string.h>
int inp[4]={0};
int flag[4]={0};
int dfs(int num)
{
if(num==24)
return 1;
for(int i=0;i<4;i++)
{
if(flag[i]==0)
{
flag[i]=1;
if(dfs(num+inp[i]))
return 1;
else if(dfs(num-inp[i]))
return 1;
else if(dfs(num*inp[i]))
return 1;
else if(dfs(num/inp[i]) && (num%inp[i]==0))
return 1;
flag[i]=0;
}
}
return 0;
}
int main()
{
while(scanf("%d %d %d %d",&inp[0],&inp[1],&inp[2],&inp[3])!=EOF)
{
memset(flag,0,sizeof(flag));
if(dfs(0))
printf("true\n");
else
printf("false\n");
}
return 0;
}
算24升级版本,列举出所有方法:
#include <stdio.h>
#define PRO_NUM 4
#define NUM_MAX_VALUE 10
struct step_t{
int p[10];
int num;
int x;
int y;
int op;
int result;
};
struct method_t{
struct step_t step[PRO_NUM];
};
struct method_t method[100] = {0};
int method_cnt = 0;
int mark = 0;
struct method_t method_tmp = {0};
int step_cnt = 0;
int isEqual(struct method_t m1, struct method_t m2)
{
int i;
int bit[1000] = {0}; //假定result范围 -500 ~ 500
int bit_tmp[1000] = {0};
for(i = 0; i < PRO_NUM - 1; i ++)
{
if(m1.step[i].result < 0)
bit[m1.step[i].result + 999]++;
else
bit[m1.step[i].result]++;
}
for(i = 0; i < PRO_NUM - 1; i ++)
{
if(m2.step[i].result < 0)
bit_tmp[m2.step[i].result + 999]++;
else
bit_tmp[m2.step[i].result]++;
}
for(i = 0; i < 1000; i++)
{
if(bit[i] != bit_tmp[i])
return -1;
}
return 0;
}
int queueIn(struct method_t m)
{
int i;
for(i = 0; i < method_cnt; i++)
{
if(isEqual(m, method[i]) == 0)
return -1;
}
method[method_cnt++] = m;
return 0;
}
void queueShow(void)
{
int i, j, k;
for(i = 0; i < method_cnt; i++)
{
printf("------------------[%d]\n", i);
for(j = 0; j < PRO_NUM - 1; j++)
{
printf("[%c][", j + 'A');
for(k = 0; k < method[i].step[j].num; k++)
{
printf("%d", method[i].step[j].p[k]);
if(k != method[i].step[j].num - 1)
printf(",");
else
printf("] ");
}
printf("%d%c%d=%d\n", method[i].step[j].x, method[i].step[j].op,
method[i].step[j].y, method[i].step[j].result);
}
}
}
#define STEP_RECORD(idx, _x, _y, _op, _re) do{\
method_tmp.step[idx].x = _x; \
method_tmp.step[idx].y = _y; \
method_tmp.step[idx].op = _op; \
method_tmp.step[idx].result = _re;\
}while(0);
int shuPro(int *p, int n)
{
int i, j, k, tmp_cnt;
int tmp[PRO_NUM] = {0};
if(n <= 1)
{
if(p[0] == 24)
{
//printf("OK\n");
queueIn(method_tmp);
mark = 1;
}
return 0;
}
else
{
for(i = 0; i < n; i ++)
for(j = 0; j < n; j++)
{
if(i != j)
{
tmp_cnt = 0;
for(k = 0; k < n; k++)
if(k != i && k != j)
tmp[tmp_cnt++] = p[k];
method_tmp.step[step_cnt].num = 0;
for(k = 0; k < n; k++)
method_tmp.step[step_cnt].p[(method_tmp.step[step_cnt].num) ++] = p[k];
tmp[tmp_cnt] = p[i] + p[j]; //加
STEP_RECORD(step_cnt, p[i], p[j], '+', tmp[tmp_cnt]);
step_cnt++;
shuPro(tmp, n - 1);
step_cnt--;
tmp[tmp_cnt] = p[i] - p[j]; //减-A
STEP_RECORD(step_cnt, p[i], p[j], '-', tmp[tmp_cnt]);
step_cnt++;
shuPro(tmp, n - 1) ;
step_cnt--;
tmp[tmp_cnt] = p[j] - p[i]; //减-B
STEP_RECORD(step_cnt, p[j], p[i], '-', tmp[tmp_cnt]);
step_cnt++;
shuPro(tmp, n - 1);
step_cnt--;
tmp[tmp_cnt] = p[i] * p[j]; //乘
STEP_RECORD(step_cnt, p[i], p[j], '*', tmp[tmp_cnt]);
step_cnt++;
shuPro(tmp, n - 1);
step_cnt--;
if(p[j] != 0 && p[i] % p[j] == 0 )
{
tmp[tmp_cnt] = p[i] / p[j]; //除A
STEP_RECORD(step_cnt, p[i], p[j], '/', tmp[tmp_cnt]);
step_cnt++;
shuPro(tmp, n - 1);
step_cnt--;
}
if(p[i] != 0 && p[j] % p[i] == 0 )
{
tmp[tmp_cnt] = p[j] / p[i]; //除B
STEP_RECORD(step_cnt, p[j], p[i], '/', tmp[tmp_cnt]);
step_cnt++;
shuPro(tmp, n - 1);
step_cnt--;
}
}
}
}
return 0;
}
void test(void)
{
int shu[] = {7,2,1,10};
method_cnt = 0;
step_cnt = 0;
shuPro(shu, 4);
queueShow();
}
int main(void)
{
int shu[PRO_NUM] = {0};
while(~(scanf("%d %d %d %d\n", shu, shu + 1, shu + 2, shu + 3)))
{
method_cnt = 0;
step_cnt = 0;
shuPro(shu, 4);
queueShow();
}
//test();
return 0;
}
16、百鸡问题(简单)
#include <stdio.h>
int main(void)
{
int i, j, k;
for(i = 0; i <= 100 / 5; i++)
{
for(j = 0; j <= (100 - i * 5) / 3; j++)
{
for(k = 0; k <= (100 - i * 5 - j * 3) * 3; k += 3)
{
if(i * 5 + j * 3 + k / 3 == 100 && i + j + k == 100)
{
printf("%d %d %d\n", i, j, k);
}
}
}
}
return 0;
}
17、成绩排名(中等)
#include <stdio.h>
#include <string.h>
//假定分数不大于100,学生数不大于100
struct data_t{
char name[100];
int score;
};
struct mg_t{
struct data_t d[100];
int num;
};
struct mg_t record[101] = {0};
int main(void)
{
int num, mode, i, j;
struct data_t d;
char name[100] = {0};
int score;
while(~(scanf("%d\n%d\n", &num, &mode)))
{
memset(record, 0, sizeof(record));
for(i = 0; i < num; i ++)
{
scanf("%s %d\n", name, &score);
strcpy(d.name, name);
d.score = score;
record[d.score].d[(record[d.score].num)++] = d;
}
if(mode == 1)
{
for(i = 0; i <= 100; i ++)
{
for(j = 0; j < record[i].num; j++)
{
printf("%s %d\n", record[i].d[j].name, record[i].d[j].score);
}
}
}
else
{
for(i = 100; i >= 0; i--)
{
for(j = 0; j < record[i].num; j++)
{
printf("%s %d\n", record[i].d[j].name, record[i].d[j].score);
}
}
}
}
return 0;
}
18、等差数列求和(简单)
公式 S(n) = n * (N(n) + N(1)) / 2
#include <stdio.h>
int main(void)
{
int num;
while(~(scanf("%d", &num)))
{
printf("%d\n", (3 * num + 1) * num / 2);
}
return 0;
}
19、走方格的方案数(简单)
#include <stdio.h>
int getNum(int x, int y)
{
if(x == 0 || y == 0)
{
return 1;
}
else
{
return getNum(x - 1, y) + getNum(x, y - 1);
}
return 0;
}
int main(void)
{
int x, y;
while(~(scanf("%d %d", &x, &y)))
{
printf("%d\n", getNum(x, y));
}
return 0;
}
20、最大的连续bit数
#include <stdio.h>
int main(void)
{
int num, i, cnt, tmp;
while(~(scanf("%d", &num)))
{
cnt = 0; tmp = 0;
for(i = 0; i < 8; i ++)
{
if((num & ((int)(1 << i))) == 0)
cnt = 0;
else
cnt++;
if(tmp < cnt)
tmp = cnt;
}
printf("%d\n", tmp);
}
return 0;
}
21、最长回字子串(简单)
/*遇到的误区:字符数组名有时候可以当做字符指针看,但是数值不能更改;例如传参用
数组名 s + 2 出逻辑错误,用指针就不会*/
#include <stdio.h>
#include <string.h>
int isOk(char *s, int n)
{
int i;
//printf("======>%c\n", s[0]);
for(i = 0; i < n / 2; i++)
{
if(s[i] != s[n - i - 1])
return -1;
}
return 0;
}
int main(void)
{
int s[1000] = {0};
int i, j, len, mark = 0;
char *p;
while(~(scanf("%s", s)))
{
p = s;
len = strlen(s);
mark = 0;
for(i = len; i > 0; i--)//子串长度
{
for(j = 0; j + i <= len; j++)//子串起始位置
{
if(isOk(p + j, i) == 0)
{
printf("%d\n", i);
mark = 1;
break;
}
}
if(mark == 1)
break;
}
//printf("%d\n", isOk(p + 2, 6));
}
return 0;
}
22、埃及分数(难)
注:想清思路便简单,要不然很难。
例子 8/11
思路是:
(1)从分子为1, 分母为1、2、3、4...按顺序取值,找到那么一个数 i 使得 1/i 小于或者等于 8/11,而且 1/(i - 1)要大于 8/11;如果是等于的,直接完成任务,否则进行下一步;
(2)从分子为1, 分母为i、i+1、i+2...按顺序取值,找到那么一个数 j使得 1/j小于或者等于 8/11 - 1/i,而且 1/(j- 1)要大于 8/11 - 1/i;如果是等于的,直接完成任务,否则继续此步骤。
(3)理论上总能找到这样的i和j,类似于渐进法。
#include <stdio.h>
struct fenshu_t{
int a;
int b;
};
int BIG(struct fenshu_t f1, struct fenshu_t f2)
{
if(f1.a * f2.b > f2.a * f1.b)
return 1;
else if(f1.a * f2.b == f2.a * f1.b)
return 0;
else
return -1;
}
struct fenshu_t ADD(struct fenshu_t f1, struct fenshu_t f2)
{
struct fenshu_t ret;
ret.a = f1.a * f2.b + f2.a * f1.b;
ret.b = f1.b * f2.b;
return ret;
}
#include <stdio.h>
int main(void)
{
int a, b, i, ret;
int num[100] = {0};
struct fenshu_t f, sum, tmp, last;
while(~(scanf("%d/%d", &a, &b)))
{
f.a = a; f.b = b; sum.a = 0; sum.b = 1, tmp.a = 1;
for(i = 2; ; i++)
{
tmp.b = i;
last = sum;
sum = ADD(sum, tmp);
ret = BIG(f, sum);
if(ret == -1)
{
sum = last;
continue;
}
else if(ret == 1)
{
printf("1/%d+", i);
}
else if(ret == 0)
{
printf("1/%d\n", i);
break;
}
}
}
return 0;
}
23、尼克切斯定理(简单)
#include <stdio.h>
int main(void)
{
int num, shu, i, j;
while(~(scanf("%d", &num)))
{
shu = num * num * num;
for(i = 1; i < shu; i += 2)
{
if((i + (i + 2 * (num - 1))) * num / 2 == shu)
{
for(j = 0; j < num; j ++)
{
if(j == num - 1)
printf("%d\n", i + 2 * j);
else
printf("%d+", i + 2 * j);
}
break;
}
}
}
return 0;
}
24、最长公共子串计算(中等)
#include <stdio.h>
#include <string.h>
int main(void)
{
char s1[1000] = {0};
char s2[1000] = {0};
int len1, len2, i, j, k, stop_mark, cnt, tmp, end;
while(~(scanf("%s\n%s\n", s1, s2)))
{
len1 = strlen(s1);
len2 = strlen(s2);
tmp = 0;
for(i = 0; i < len1; i++)
{
for(j = 0; j <= len2; j++)
{
stop_mark = 0; cnt = 0; end = (len1 - i) < (len2 - j)?(len1 - i):(len2 - j);
for(k = 0; k < end; k++)
{
if(s1[i + k] != s2[j + k])
stop_mark = 1;
else
cnt++;
if(tmp < cnt)
tmp = cnt;
if(stop_mark == 1)
break;
}
}
}
printf("%d\n", tmp);
}
return 0;
}
25、参数解析(中等)
#include <stdio.h>
#include <string.h>
int main(void)
{
char s[1000] = {0};
int i, last, len, cnt, mark;
char *p;
while(gets(s) != NULL)
{
last = 0; p = s; len = strlen(s); cnt = 0;
mark = 0;
for(i = 0; i < len; i++)
{
if(s[i] == '"')
mark = !mark;
if(s[i] == ' ' && mark == 0)
cnt++;
}
printf("%d\n", cnt + 1);
for(i = 0; i < len; i++)
{
if(s[i] == '"')
{
i++;
while(s[i] != '"' && i < len)
{
printf("%c", s[i]);
i++;
}
i++;
}
if(s[i] == ' ')
{
printf("\n");
continue;
}
printf("%c", s[i]);
}
}
return 0;
}
26、日期和天数的转换(简单)
#include <stdio.h>
int isRunNian(int num)
{
if(num % 4 == 0 && num % 100 != 0)
return 0;
return -1;
}
const int mouth_day[]={
31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
int main(void)
{
int y, m, d, i, sum;
while(~(scanf("%d %d %d\n", &y, &m, &d)))
{
sum = 0;
for(i = 0; i < m - 1; i++)
sum += mouth_day[i];
sum += d;
if(m > 2 && isRunNian(y) == 0)
sum++;
printf("%d\n", sum);
}
return 0;
}
27、矩阵相乘(中等)
#include <stdio.h>
int main(void)
{
int A_x, A_y, B_z, i, j, k;
int AA[10000] = {0};
int BB[10000] = {0};
int CC[10000] = {0};
int *A, *B, *C;
while(~(scanf("%d\n%d\n%d\n", &A_x, &A_y, &B_z)))
{
A = AA; B = BB; C = CC;
for(i = 0 ; i < A_x * A_y; i++)
scanf("%d", A + i);
for(i = 0 ; i < A_y * B_z; i++)
scanf("%d", B + i);
for(i = 0; i < A_x ; i++)
{
for(j = 0; j < B_z; j++)
{
C[i * B_z + j] = 0;
for(k = 0; k < A_y; k++)
{
C[i * B_z + j] += A[i * A_y + k] * B[k * B_z + j];
}
}
}
for(i = 0 ; i < A_x * B_z; i++)
{
printf("%d", C[i]);
if((i + 1) % B_z == 0)
printf("\n");
else
printf(" ");
}
}
return 0;
}
28、矩阵乘法计算估量(略难)
#include <stdio.h>
struct matrix_t{
int x;
int y;
};
struct matrix_t mat[100] = {{0},};
int multiTimes(struct matrix_t m1, struct matrix_t m2, struct matrix_t *out)
{
out->x = m1.x; out->y = m2.y;
return m1.x * m1.y * m2.y;
}
int g_pos = 0;
int funPro(char *s, struct matrix_t *out)
{
int mark1, mark2, cnt;
struct matrix_t m1, m2;
cnt = 0; mark1 = 0; mark2 = 0;
while(s[g_pos] != '\0')
{
if(s[g_pos] == '(')
{
g_pos++;
if(mark1 == 0)
{
cnt += funPro(s , &m1);
mark1 = 1;
}
else if(mark1 == 1 && mark2 == 0)
{
cnt += funPro(s , &m2);
mark2 = 1;
}
}
else if(s[g_pos] == ')')
{
//printf("==>m1.x=%d m1.y=%d m2.x=%d m2.y=%d\n", m1.x, m1.y, m2.x, m2.y);
if(mark1 == 1 && mark2 ==1)
cnt += multiTimes(m1, m2, out);
return cnt;
}
else if(s[g_pos] >= 'A' && s[g_pos] <= 'Z')
{
if(mark1 == 0)
{
m1 = mat[s[g_pos] - 'A'];
mark1 = 1;
}
else if(mark1 == 1 && mark2 == 0)
{
m2 = mat[s[g_pos] - 'A'];
mark2 = 1;
}
}
g_pos++;
}
return cnt;
}
int main(void)
{
int num, i, mark;
char s[256] = {0};
char *p;
struct matrix_t m;
while(~(scanf("%d", &num)))
{
p = s;
for(i = 0; i < num; i++)
scanf("%d %d\n", &(mat[i].x), &(mat[i].y));
scanf("%s", s);
g_pos = 0;
printf("%d\n", funPro(p, &m));
}
return 0;
}
29、字符通配符(难,参考网友)
/*
参考网友
采用递归的思路。从前向后依次匹配:
遇到相同字符,都向后移动一个字符;
如果通配符遇到"?",则不需匹配,自动跳过一个字符;
如果通配符遇到"*",则可以匹配任意多个字符,包括0个,此时可以有三种选择:
1.匹配0个,通配符向后移动一个字符,字符串不动;
2.匹配1个,通配符和字符串都向后移动一个字符;
3.匹配多个,通配符不动,字符串向后移动一个字符。
递归的终止条件:通配符或者字符串遇到'\0'。表示同时结束,返回true。
*/
#include <stdio.h>
#include <string.h>
int match(char *s1, char *s2)
{
if(s1[0] == '\0' && s2[0] != '\0')
return 0;
else if(s1[0] != '\0' && s2[0] == '\0')
return 0;
else if(s1[0] == '\0' && s2[0] == '\0')
return 1;
else if(s1[0] == '?')
return match(s1 + 1, s2 + 1);
else if(s1[0] == '*')
return match(s1 + 1, s2) || match(s1 + 1, s2 + 1) || match(s1, s2 + 1);
else if(s1[0] == s2[0])
return match(s1 + 1, s2 + 1);
return 0;
}
int main(void)
{
char s1[1000] = {0};
char s2[1000] = {0};
while(~(scanf("%s\n%s", s1, s2)))
{
char p1, p2;
p1 = s1; p2 = s2;
if(match(s1, s2) == 1)
printf("true\n");
else
printf("false\n");
}
return 0;
}
30、火车进站(难)
难就一个字
我的程序说明:
(1)排序操作耗费了时间;
(2)应用到了BFS(广度优先搜索)、递归、栈的思想;
(3)递归运算里,广度优先代表着遍历所有可能,有两个分支的点,进入分支前要先保存栈,出来后恢复栈;如果是深度优先的话,在满足某情况下直接 return 了(参考 “算24“的例子)
#include <stdio.h>
#include <string.h>
struct data_t{
int stack[20];
int s_n;
int record[20];
int r_n;
};
struct data_t data;
void stackInit(void)
{
memset(&data, 0, sizeof(data));
}
void stackPop(void)
{
if(data.s_n > 0)
data.record[data.r_n++] = data.stack[--data.s_n];
}
void stackPush(int val)
{
data.stack[data.s_n++] = val;
}
void stackResultPrint(struct data_t d)
{
int i;
for(i = 0; i < d.r_n; i++)
printf("%d ", d.record[i]);
for(i = d.s_n - 1; i >= 0; i--)
{
printf("%d", d.stack[i]);
if(i == 0)
printf("\n");
else
printf(" ");
}
}
//排序
struct data_t array[10000];
int array_cnt = 0;
int BIG(struct data_t d1, struct data_t d2)
{
int len = d1.r_n + d1.s_n;
int a[20] = {0};
int b[20] = {0};
int cnt, i;
cnt = 0;
for(i = 0; i < d1.r_n; i++)
a[cnt++] = d1.record[i];
for(i = d1.s_n - 1; i >= 0; i--)
a[cnt++] = d1.stack[i];
cnt = 0;
for(i = 0; i < d2.r_n; i++)
b[cnt++] = d2.record[i];
for(i = d2.s_n - 1; i >= 0; i--)
b[cnt++] = d2.stack[i];
for(i = 0; i < len; i++)
{
if(a[i] > b[i])
return 0;
else if(a[i] < b[i])
return -1;
}
return -1;
}
void sort(void)
{
int i, j;
struct data_t tmp;
for(i = 0; i < array_cnt - 1; i++)
{
for(j = 0; j < array_cnt - i - 1; j++)
{
if(BIG(array[j], array[j + 1]) == 0)
{
//printf("-----\n");
//stackResultPrint(array[j]); stackResultPrint(array[j + 1]);
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
for(i = 0; i < array_cnt; i++)
stackResultPrint(array[i]);
}
int BFS(int *p, int n)
{
struct data_t last_data;
if(n == 0)
{
array[array_cnt++] = data;
//stackResultPrint();
}
else
{
//分叉1
if(data.s_n > 0)
{
last_data = data;
stackPop();
BFS(p, n);
data = last_data;
}
//分叉2
last_data = data;
stackPush(p[0]);
BFS(p + 1, n - 1);
data = last_data;
}
return 0;
}
int main(void)
{
int num;
int shu[100] = {0};
int i;
while(~(scanf("%d", &num)))
{
for(i = 0; i < num; i++)
scanf("%d ", shu + i);
stackInit();
array_cnt = 0;
BFS(shu, num);
sort();
}
return 0;
}
31、整形数组合并(简单)【可分析网友思路】
位图法
#include <stdio.h>
#define MAX_LEN 1000
#define MAX_NUM 100000
int main(void)
{
int len_a, len_b, i;
int A[MAX_LEN] = {0};
int B[MAX_LEN] = {0};
int bitmap[2 * MAX_NUM] = {0};
while(~(scanf("%d", &len_a)))
{
for(i = 0; i < len_a; i++)
scanf("%d ", A + i);
scanf("%d ", &len_b);
for(i = 0; i < len_b; i++)
scanf("%d ", B + i);
for(i = 0; i < 2 * MAX_NUM; i++)
bitmap[i] = 0;
for(i = 0; i < len_a; i++)
bitmap[A[i] + MAX_LEN] = 1;
for(i = 0; i < len_b; i++)
bitmap[B[i] + MAX_LEN] = 1;
for(i = 0; i < 2 * MAX_NUM; i++)
if(bitmap[i] == 1)
printf("%d", i - MAX_LEN);
printf("\n");
}
return 0;
}
32、字符串字符匹配(简单)
#include <stdio.h>
#include <string.h>
int main(void)
{
char s1[1000] = {0};
char s2[1000] = {0};
int bit[256] = {0};
int i, mark;
while(~(scanf("%s\n%s", s1, s2)))
{
for(i = 0; i < 256; i++)
bit[i] = 0;
for(i = 0; i < strlen(s2); i++)
bit[s2[i]] = 1;
mark = 0;
for(i = 0; i < strlen(s1); i++)
if(bit[s1[i]] != 1)
{
mark = 1;
break;
}
if(mark == 1)
printf("false\n");
else
printf("true\n");
}
return 0;
}
33、扑克牌大小比较(中等)
比较繁琐
#include <stdio.h>
#include <string.h>
struct data_t{
int a[10];
int n;
int type; //0 个牌;1 对子; 2 三牌顺子; 3 五牌顺子; 4 普通炸; 5 王炸; -1 数据无效
};
enum type_t{
type_one = 0,
type_pair,
type_three,
type_five,
type_boom,
type_kingBoom,
type_error = -1
};
#define PUK_NUM 15
#define NAME_MAX_SIZE 6
#define TYPE_MAX_NUM 10
const char puk[15][NAME_MAX_SIZE]={
"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2","joker", "JOKER"
};
int wight_map[TYPE_MAX_NUM] = {0};
void weightMap(void)
{
wight_map[type_one] =
wight_map[type_pair] =
wight_map[type_three] =
wight_map[type_five] = 1;
wight_map[type_boom] = 2;
wight_map[type_kingBoom] = 3;
}
int pukToNum(char *s)
{
int i;
for(i = 0; i < PUK_NUM; i++)
if(strcmp(puk[i], s) == 0)
return i;
return -1;
}
int pukSetType(struct data_t *p)
{
if(p->n == 1)
p->type = type_one;
else if(p->n == 2)
{
if(p->a[0] == pukToNum("joker") || p->a[0] == pukToNum("JOKER"))
p->type = type_kingBoom;
else
p->type = type_pair;
}
else if(p->n == 3)
p->type = type_three;
else if(p->n == 4)
p->type = type_boom;
else if(p->n == 5)
p->type = type_five;
else
{
p->type = type_error;
return -1;
}
return 0;
}
void pukPrint(struct data_t p)
{
int i;
for(i = 0; i < p.n; i++)
{
printf("%s", puk[p.a[i]]);
if(i == (p.n - 1))
printf("\n");
else
printf(" ");
}
}
int BIG(struct data_t p1, struct data_t p2)
{
if( !((p1.type >= type_one && p1.type <= type_kingBoom) &&
(p2.type >= type_one && p2.type <= type_kingBoom)))
return -1;
if(wight_map[p1.type] > wight_map[p2.type])
return 1;
else if(wight_map[p1.type] < wight_map[p2.type])
return 0;
else if(wight_map[p1.type] == wight_map[p2.type] &&
p1.type == p2.type)
{
if(p1.a[0] > p2.a[0])
return 1;
else
return 0;
}
return -1;
}
int pukAnly(char *s, struct data_t *p1, struct data_t *p2)
{
char tmp[NAME_MAX_SIZE] = {0};
int i, tmp_cnt;
struct data_t *p;
memset(p1, 0, sizeof(struct data_t));
memset(p2, 0, sizeof(struct data_t));
i = 0; tmp_cnt = 0; p = p1;
while(s[i] != '\0')
{
if(s[i] == ' ')
{
tmp[tmp_cnt] = '\0';
p->a[p->n++] = pukToNum(tmp);
tmp_cnt = 0;
}
else if(s[i] == '-')
{
tmp[tmp_cnt] = '\0';
p->a[p->n++] = pukToNum(tmp);
tmp_cnt = 0; p = p2;
}
else
tmp[tmp_cnt++] = s[i];
i++;
}
tmp[tmp_cnt] = '\0';
p->a[p->n++] = pukToNum(tmp);
return 0;
}
int main(void)
{
char s[256] = {0};
struct data_t p1, p2;
weightMap();
int ret;
while(gets(s) != NULL)
{
pukAnly(s, &p1, &p2);
pukSetType(&p1); pukSetType(&p2);
ret = BIG(p1, p2);
//printf("%d-%d-%d %d-%d-%d %d\n", p1.a[0], p1.n, p1.type, p2.a[0], p2.n, p2.type, BIG(p1, p2));
if(ret == 1)
pukPrint(p1);
else if(ret == 0)
pukPrint(p2);
else
printf("ERROR\n");
}
return 0;
}
34、扑克牌算24(难)
由于体量比较小,所以用到了穷举法;
健壮性不够;
#include <stdio.h>
#include <string.h>
const char puk[15][6]={
"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2","joker", "JOKER"
};
const int puk_map[15]={
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 14, 15
};
int pukToNum(char *s)
{
int i;
for(i = 0; i < 15; i++)
if(strcmp(puk[i], s) == 0)
return puk_map[i];
return -1;
}
int numToPuk(int n, char *out)
{
int i;
for(i = 0; i < 15; i++)
if(puk_map[i] == n)
{
strcpy(out, puk[i]);
return 0;
}
return -1;
}
int isRepeat(int *p, int n)
{
int j;
int tmp[10] = {0};
//查重
for(j = 0; j < n; j ++)
tmp[j] = 0;
for(j = 0; j < n; j ++)
tmp[p[j]] = 1;
for(j = 0; j < n; j ++)
if(tmp[j] == 0)
return 1;
return 0;
}
int calc(int *shu, int *p)//默认7个元素
{
int sum = shu[p[0]];
//printf("==>sum=%d\n", sum);
int i, num, op;
for(i = 1; i < 4; i++)
{
num = shu[p[2 * i]]; op = p[2 * i - 1];
//printf("==>op=%d\n", op);
if(op == 0)
sum += num;
else if(op == 1)
sum -= num;
else if(op == 2)
sum *= num;
else if(op == 3)
{
if(num == 0)
return -1;
if((sum % num) != 0)
return -1;
sum /= num;
}
}
return sum;
}
const char operator[]={'+', '-', '*', '/'};
int main(void)
{
char s[4][6] = {{0},};
char out[6] = {0};
int inp[4] = {0};
int i, mark, j;
int tmp[7] = {0};
int tmp4[4] = {0};
int tmp3[3] = {0};
while(~(scanf("%s %s %s %s\n", s, s + 1, s + 2, s + 3)))
{
mark = 0;
for(i = 0; i < 4; i++)
{
inp[i] = pukToNum(s[i]);
if(inp[i] == -1 || inp[i] == 14 || inp[i] == 15)
{
printf("ERROR\n");
mark = 1;
break;
}
}
//法1
//4个项(每个项4种选择),3个运算符(每个运算符4个选择),排列组合穷举式子需16384次(4的7次方)
//相当于4进制数,而4可以用 1 << 2 表示
mark = 0;
for(i = 0; i < (1 << (2 * 7)); i++)
{
for(j = 0; j < 7; j ++)
tmp[j] = (i % (1 << (2 * (7 - j)))) / (1 << (2 * (6 - j)));
for(j = 0; j < 4; j ++)
tmp4[j] = tmp[2 * j];
if(isRepeat(tmp4, 4))
continue;
/*for(j = 0; j < 7; j ++)
if(j % 2 == 0)
printf("%d", inp[tmp[j]]);
else
printf("%c", operator[tmp[j]]);
printf("=%d\n", calc(inp, tmp));*/
if(calc(inp, tmp) == 24)
{
mark = 1;
break;
}
}
if(mark == 1)
{
for(j = 0; j < 7; j ++)
if(j % 2 == 0)
{
numToPuk(inp[tmp[j]], out);
printf("%s", out);
}
else
printf("%c", operator[tmp[j]]);
}
else
printf("NONE\n");
}
return 0;
}
35、合法ip(简单)
#include <stdio.h>
int main(void)
{
char s[1000] = {0};
int num[4] = {0};
char str[4][32] = {0};
int i, mark, cnt, cnt2;
while(gets(s) != NULL)
{
sscanf(s, "%d.%d.%d.%d", num, num + 1, num + 2, num + 3);
//sscanf(s, "%s.%s.%s.%s", str[0], str[1], str[2], str[3]);
i = 0; cnt = 0, cnt2 = 0;
while(s[i] != '\0')
{
if(s[i] == '.')
{
str[cnt][cnt2] = '\0';
cnt++; cnt2 = 0;
if(cnt >= 4)
break;
}
else
str[cnt][cnt2++] = s[i];
i++;
}
str[cnt][cnt2] = '\0';
//printf("s=%s \n", str[0]);
mark = 0;
for(i = 0; i < 4; i++)
{
if(num[i] < 0 || num[i] > 255 ||
(num[i] == 0 && !(str[i][0] == '0' && str[i][1] == '\0')) )
{
mark = 1;
break;
}
}
if(mark == 1)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
36、字符串中找到连续为数字的最长子串(简单)
#include <stdio.h>
#include <string.h>
struct data_t{
int pos;
int len;
};
int main(void)
{
char s[1000] = {0};
struct data_t tmp, current;
struct data_t array[100];
int array_cnt, i, j, len;
char last;
while(gets(s) != NULL)
{
array_cnt = 0; tmp.pos = 0; tmp.len = 0; current = tmp;
i = 0; last = s[0];
len = strlen(s); s[len] = 'a'; s[len + 1] = '\0'; //添加一个字母
while(s[i] != '\0')
{
if(s[i] >= '0' && s[i] <= '9')
{
if(!(last >= '0' && last <= '9'))
{
current.pos = i;
current.len = 1;
}
else
current.len++;
}
else
{
if(last >= '0' && last <= '9')
{
if(tmp.len == current.len)
{
array[array_cnt++] = current;
}
else if(tmp.len < current.len)
{
array_cnt = 1;
array[0] = current;
tmp = current;
}
}
}
last = s[i];
i++;
}
for(i = 0; i < array_cnt; i++)
for(j = 0; j < array[i].len; j++)
printf("%c", s[array[i].pos + j]);
printf(",%d\n", array[0].len);
}
return 0;
}
37、数组分组(中等)
#include <stdio.h>
int arraySum(int *p, int n)
{
int i, ret;
ret = 0;
for(i = 0;i < n; i++)
ret += p[i];
return ret;
}
int absoluteVal(int a)
{
if(a < 0)
return -a;
return a;
}
int main(void)
{
int num, i, j;
int IN[100] = {0};
int A5[100] = {0}; //5的倍数为一组
int A3[100] = {0}; //3的倍数为一组
int B[100] = {0}; //其他的为一组(B分两组,这两组和的差值 与 A5、A3和的差值相等,则符合题设)
int cntA5, cntA3, cntB, diff, sum, sum_sub, mark;
while(~(scanf("%d", &num)))
{
for(i = 0; i < num; i++)
scanf("%d\n", IN + i);
cntA5 = cntA3 = cntB = 0;
for(i = 0; i < num; i++)
{
if(IN[i] % 5 == 0)
A5[cntA5++] = IN[i];
else if(IN[i] % 3 == 0)
A3[cntA3++] = IN[i];
else
B[cntB++] = IN[i];
}
diff = absoluteVal(arraySum(A5, cntA5) - arraySum(A3, cntA3));
sum = arraySum(B, cntB);
//组合问题,最多 2^n 次方个,注意n不可超过31个,一是int范围有限,二是耗时久
mark = 0;
for(i = 0; i < ((int)1 << (cntB + 1)); i++)
{
sum_sub = 0;
for(j = 0; j < cntB; j++)
{
if((i & (1 << j)) != 0)
sum_sub += B[j];
}
if(absoluteVal(2 * sum_sub -sum) == diff)
{
mark = 1;
break;
}
}
if(mark == 1)
printf("true\n");
else
printf("false\n");
}
return 0;
}
38、计票统计(简单)
#include <stdio.h>
#include <string.h>
int main(void)
{
int num1, num2, i, j, error, mark;
char A[100][64] = {{0},};
char B[100][64] = {{0},};
int cntA[100] = {0};
while(~(scanf("%d\n", &num1)))
{
for(i = 0; i < 100; i++)
cntA[i] = 0;
for(i = 0; i < num1; i++)
scanf("%s ", A[i]);
scanf("%d\n", &num2);
for(i = 0; i < num2; i++)
scanf("%s", B[i]);
error = 0;
for(i = 0; i < num2; i++)
{
mark = 0;
for(j = 0; j < num1; j++)
{
if(strcmp(A[j], B[i]) == 0)
{
cntA[j]++;
mark = 1;
break;
}
}
if(mark == 0)
error++;
}
for(i = 0; i < num1; i++)
printf("%s : %d\n", A[i], cntA[i]);
printf("Invalid : %d\n", error);
}
return 0;
}
网友评论