一.找素数
1.题目概述
打印出所有在100到200之间的素数
2.解法
①暴力求解
#include<math.h> #include<stdio.h> int main() { int i = 0; for (i = 100; i <= 200; i++) { //判断i是否是素数 int j = 0; int flag = 1; for (j = 2; j <i; j++) { if (i % j == 0) { flag = 0; break; } } if (1==flag) printf("%d ", i); } return 0; }
很多新手，包括我都会这样求解，但其实这种解法，并没优化，即没多考虑素数的性质
②优化求解
要想优化，可以在多想点素数的性质，首先，一个数要是质数，得至少有两个公因数，基于这一点，可以先优化，j的取值范围缩小到sqrt(i).
其次，还要考虑一点，一个数要是质数，那么它必定不是偶数，所以再次对i优化，故可得代码段
#include<math.h> #include<stdio.h> int is_prime(int n) { int j = 0; //优化2 for (j = 2; j <= sqrt(n); j++) { if (n % j == 0) { return 0;//return 速度优于break } } return 1; } int main() { //是素数打印 int i = 0; int count = 0; //优化1 for (i = 101; i <= 200; i += 2) { if (is_prime(i)) { printf("%d ", i); count++; } } printf("\ncount=%d\n", count); return 0; }
二.二分查找
这个题目相对简单，算是复习吧，不过其中唯一的更新算是，有个小技巧，防止溢出
int binary_search(int arr[], int k, int sz) { //先想好怎么用 int left = 0; int right = sz - 1; while (left <= right) { //int mid = (left + right) / 2;不用这个，防止溢出 int mid = left + (right - left) / 2; if (arr[mid] > k) //在左边 right = mid - 1; else if (arr[mid] < k) left = mid + 1; else return mid; } return -1; } int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; int k = 1; int sz = sizeof(arr) / sizeof(arr[0]); //找到了返回下标 //找不到返回？不能是0，因为下标有0，返回-1 int ret=binary_search(arr,k,sz); if (ret != -1) printf("找到了，下标是:>%d\n", ret); else printf("找不到\n"); return 0; }
三.打印空心正方形(来自牛客网)
题目概述：KiKi学习了循环，BoBo老师给他出了一系列打印图案的练习，该任务是打印用“*”组成的“空心”正方形图案。
输入描述：
多组输入，一个整数（3~20），表示输出的行数，也表示组成正方形边的“*”的数量。
输出描述：
针对每行输入，输出用“*”组成的“空心”正方形，每个“*”后面有一个空格。
①.暴力算法
#include<stdio.h> int main() { int intm, i, j; while (scanf("%d", &intm) != 0) { for (i = 1; i <= intm; i++) { printf("* "); } printf("\n"); for (i = 1; i <= intm - 2; i++) { printf("* "); for (j = 1; j <= intm - 2; j++) { printf(" "); } printf("*\n"); } for (i = 1; i <= intm; i++) { printf("* "); } printf("\n"); } return 0; }
这个真是比较笨的算法了，一行一行打印，不仅低效，而且极耗空间。
②.稍微优化
#include<stdio.h> int main() { int intm, i, j; while (scanf("%d", &intm) != 0) { for (i = 1; i <= intm; i++) { for (j = 1; j <= intm; j++) { if (i == 1 || i == intm || j == 1 || j == intm) printf("* "); else printf(" "); } printf("\n"); } } return 0; }
这个算法就相对高明不少了，首先我们想明白问题的性质，实在n*n的大方块放置'*'和' ',所以我们要想*怎么放置，无非就是 i == 1 || i == intm || j == 1 || j == intm这一部分了。所以这个代码写的就相对不错了。
四.空心三角形(来自牛客网)
题目概述：KiKi学习了循环，BoBo老师给他出了一系列打印图案的练习，该任务是打印用“*”组成的“空心”三角形图案。
输入描述：
多组输入，一个整数（3~20），表示输出的行数，也表示组成三角形边的“*”的数量。
输出描述：
针对每行输入，输出用“*”组成的“空心”三角形，每个“*”后面有一个空格。
①.暴力求解
#include<stdio.h> int main() { int intm,i,j; while(scanf("%d",&intm)!=EOF) { printf("*\n"); for(i=2;i<=intm-1;i++) { printf("* "); for(j=1;j<=i-2;j++) { printf(" "); } printf("*\n"); } for(j=1;j<=intm;j++) { printf("* "); } printf("\n"); } return 0; }
这个和上述差不多，也是一行一行敲，特别简陋。
②优化算法
#include<stdio.h> int main() { int intm,i,j; while(scanf("%d",&intm)!=EOF) { //行 for(i=1;i<=intm;i++) { //列 for(j=1;j<=i;j++) { if(i>2&&i<intm&&j>1&&j<i) { printf(" "); } else printf("* "); } printf("\n"); } } return 0; }
这种解法就优化不少，问题我们反过来思考，如果不好考虑'*'怎么放置，不妨反过来思考' ',所谓正难则反。
五.X形图案
题目概述：
KiKi学习了循环，BoBo老师给他出了一系列打印图案的练习，该任务是打印用“*”组成的X形图案。
输入描述：
多组输入，一个整数（2~20），表示输出的行数，也表示组成“X”的反斜线和正斜线的长度。
输出描述：
针对每行输入，输出用“*”组成的X形图案。
这道题目笔者在之前做了正斜形和反斜形。所以一直想着可以将两者结合求解，但是也没能整出个所以然，而且十分繁琐。所以换个角度，从数学的角度进行思考。方才解惑
int main() { int intm, i, j; while (scanf("%d", &intm) != 0) { //找规律 for (i = 1; i <= intm; i++)//外循环 { for (j = intm; j >= 1; j--)//内循环 { if (i == j || i + j == intm + 1) { printf("*"); } else printf(" "); } printf("\n"); } }
仔细思考'*'的放置，就可以发现i和j的关系就是在i=j和i+j=intm+1处有'*'.
