| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 12336 人关注过本帖, 41 人收藏
标题:C语言循环的小艺术(质数判断,菱形打印,奇数阶幻方,字符串循环移位)
只看楼主 加入收藏
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
结帖率:96.15%
收藏(41)
已结贴  问题点数:0 回复次数:90 
C语言循环的小艺术(质数判断,菱形打印,奇数阶幻方,字符串循环移位)
写代码,有两类追求,一种是追求实用(Coder),一种是追求代码艺术(Artist)
我是那种追实用追腻了,偶然追一下艺术(就是偶然和艺术有一腿)的那种Coder


很多人,已经习惯了for(i=0; i<n; i++)这种单调的循环,虽然这的确的使用率最高,
但在特殊场合,特殊的循环写法,不但能提升循环的效率,还能使代码更精巧

1. 质数判断
对于这个,很多人可能会直接这样写:
int isPrime(int n) //函数返回1表示是质数,返回0表示不是质数
{
    int i;
    for (i = 2; i < n; i++)
        if (n % i == 0)
            break;
    return i >= n;
}

又或者,有的人知道平方根的优化:
int isPrime(int n)
{
    int i, s = (int)(sqrt((double)n) + 0.01);
    for (i = 2; i <= s; i++)
        if (n % i == 0)
            break;
    return i > s;
}

再或者,消除偶数:
int isPrime(int n)
{
    int i, s = (int)(sqrt((double)n) + 0.01);
    if (n <= 3) return 1;
    if (n % 2 == 0) return 0;
    for (i = 3; i <= s; i += 2)
        if (n % i == 0)
            break;
    return i > s;
}

当然,这样还不是很够的话,我们可以考虑这个事实:
所有大于4的质数,被6除的余数只能是1或者5
比如接下来的5,7,11,13,17,19都满足

所以,我们可以特殊化先判断2和3
但后面的问题就出现了,因为并非简单的递增,从5开始是+2,+4,+2,+4,....这样递增的
这样的话,循环应该怎么写呢?

首先,我们定义一个步长变量step,循环大概是这样 for (i = 5; i <= s; i += step)
那么,就是每次循环,让step从2变4,或者从4变2
于是,可以这么写:

#include <stdio.h>
#include <math.h>

int isPrime(int n)
{
    int i, s = (int)(sqrt((double)n) + 0.01), step = 4;
    if (n <= 3) return 1;
    if (n % 2 == 0) return 0;
    if (n % 3 == 0) return 0;
    for (i = 5; i <= s; i += step)
    {
        if (n % i == 0)
            break;
        step ^= 6;
    }
    return i > s;
}

int main()
{
    int n;
    for (n = 2; n < 100; ++n) //找出 2 - 100 的质数并输出
    {
        if (isPrime(n)) printf("%d,", n);
    }
    getchar();
    return 0;
}

如上代码,一个 step ^= 6; 完成step在2和4之间转换(这个 ^ 符号是C里的异或运算)
理由是,2化二进制是010,4是100,6是110,于是2异或4得到6:
2 ^ 4 => 6
6 ^ 2 => 4
6 ^ 4 => 2

于是利用异或,就可以构造这种步长在两个值之间来回变化的循环
思考题:前面说的是双值循环,那么如何构造三值或者四值循环?








2.菱形打印

很多人,打印菱形在控制台的思路是,把菱形上下拆分,分两段很接近的代码来打印,
其实这样代码很不好看,并且不好阅读
我们知道,要打印的图案是这种:
    *
   ***
  *****
   ***
    *

满足上下对称,左右对称,那么,你能不能也弄一个二重循环,同样是对称的?
很简单,首先我们要抛开习惯性思维,for循环不一定要在0开始或者0结束
我们可以让循环从 -c 到 c ,这样不就轻松产生一个对称的吗?(只要取个绝对值)
我们把菱形的中心看成是坐标0,0,那么,会输出星号的坐标,是 |x| + |y| <= c 的点

由此可得
#include <stdio.h>
#define IABS(x) ( (x) >= 0 ? (x) : -(x) ) //定义一个计算绝对值的宏
void print(int size) // size是这个菱形的半径,直径会是size * 2 + 1
{
    int x, y;
    for (y = -size; y <= size; y++)
    {
        for (x = -size; x <= size; x++)
        {
            if ( IABS(x) + IABS(y) <= size ) //x和y各自的绝对值的和,即 |x| + |y| <= size
                putchar('*');
            else
                putchar(' ');
        }
        putchar('\n');
    }
}

int main()
{
    print(5); //输出一个半径为5的菱形
    getchar();
    return 0;
}

如果我需要得到空心菱形呢?非常非常简单,因为菱形边界上的点,满足的是|x| + |y| == c
所以,我们只要把那个if里的小于等于号,改成双等于号 == 就可以了

再类似地,如果我不要*号,我要最外层是字母A,然后里一层是B这样呢?即:
    A
   ABA
  ABCBA
   ABA
    A

那么,我们只要在putchar那里做一个字符计算:
void print(int size) // size是这个菱形的半径,直径会是size * 2 + 1
{
    int x, y;
    for (y = -size; y <= size; y++)
    {
        for (x = -size; x <= size; x++)
        {
            if ( IABS(x) + IABS(y) <= size ) //x和y各自的绝对值的和,即 |x| + |y| <= size
                putchar( 'A' + (size - IABS(x) - IABS(y)) ); //留意这里的计算方法
            else
                putchar(' ');
        }
        putchar('\n');
    }
}

类似地,如果我们要打印的是X形:
  *   *
   * *
    *
   * *
  *   *
同样可以利用这个思路完成,这题就作为思考题吧








3. 奇数阶幻方
所谓幻方(最基本的那种),就是横,竖,对角线上的数的和等于一个常数的数字方阵
4 3 8
9 5 1
2 7 6

以上这个图,有什么规律?容易写成代码吗?

我们把这个图,向右复制五次,向下复制三次,展开一下:

4 3 8 4 3 8 4 3 8 4 3 8 4 3 8
9 5 1 9 5 1 9 5 1 9 5 1 9 5 1
2 7 6 2 7 6 2 7 6 2 7 6 2 7 6
4 3 8 4 3 8 4 3 8 4 3 8 4 3 8
9 5 1 9 5 1 9 5 1 9 5 1 9 5 1
2 7 6 2 7 6 2 7 6 2 7 6 2 7 6
4 3 8 4 3 8 4 3 8 4 3 8 4 3 8
9 5 1 9 5 1 9 5 1 9 5 1 9 5 1
2 7 6 2 7 6 2 7 6 2 7 6 2 7 6

注意蓝色数字的走向
怎么样,现在呢?
现在看起来显得规律性强了很多,但是,你会不会觉得循环还是不太好写?
我们如何从一个给定的n,直接得知它的坐标呢?
不难,找一下规律就可以发现对于任意的数值n+1有(以左上角为0,0坐标):
x = 2 + n + n / 3;
y = 1 + n - n / 3;

其实这个规律可以简单扩展到任意奇数阶幻方(以下size是奇数):
x = size / 2 + 1 + n + n / size; (注意这里的除法是取整除法,不带小数)
y = size / 2     + n - n / size;

这样,我们就可以把原来复杂的循环,化简成一重简单循环

于是有程序:
#include <stdio.h>
#define SIZE 5  //定义幻方阶数,这个数只能是奇数
int main()
{
    int x, y, i, sqSize, hSize;
    int sqMap[SIZE][SIZE];
    sqSize = SIZE * SIZE;
    hSize  = SIZE / 2;
    //计算1至SIZE * SIZE的数的位置并记录
    for ( i = 0; i < sqSize; i++)
    {
        x = hSize + 1 + i + i / SIZE;
        y = hSize     + i - i / SIZE;
        sqMap[y % SIZE][x % SIZE] = i + 1;
    }
    //以下是输出
    for (y = 0; y < SIZE; y++)
    {
        for (x = 0; x < SIZE; x++)
            printf("%4d", sqMap[y][x]);
        puts("");
    }
    return 0;
}


这个比你网上能找到的很多求奇数阶幻方的代码都短小很多(不过网上较多称之为魔方阵,不知为何)








4. 字符串循环移位

问题,给你一个字符串,要求循环左移n位
比如对"abcdefg" 循环左移2位,我们要得到"cdefgab"

附加条件,不能使用连续辅助空间(包括动态分配),只能使用若干单个变量(即O(1)空间)

首先,我们知道,反转一个字符串操作("abcd"变"dcba"),是不需要额外数组辅助的,只要头尾数据交换就可以了
然而,可能你不知道,仅仅使用字符串反转可以实现字符串循环移位:

//反转字符串,把st与ed所指向的中间的内容反转(包含st不包含ed)
void str_rev(char* st, char *ed)
{
    for (--ed; st < ed; ++st, --ed)
    {
        char c;
        c = *st; *st = *ed; *ed = c;
    }
}

//用三反转等效左移字符串(st与ed之间,包含st不包含ed的内容)
char* str_shl(char* st, char* ed, int n)
{
    str_rev(st, &st[n]);
    str_rev(    &st[n], ed);
    str_rev(st,         ed);
    return st;
}

#include <stdio.h>
#include <string.h>
int main()
{
    char str[] = "abcdefghijklmnopqrstuvwxyz";
    puts( str_shl(str, str + strlen(str), 6) );
    getchar();
    return 0;
}

这里,如果要循环左移n位,只要把原来字符串分成两段,前n字符,和后面其它字符
两段分别反转,最后再整体反转,就实现了循环左移(如果先整体再两部分,就是循环右移)

而在那个字符串反转函数里,参与循环的,不再是int,而是两个指针,
为什么选择使用两个指针呢?如果你写一个str_rev(char* str, int len)的版本,相信你就明白了,这里不多废话


好了,先写这么多,其它的留下次了,xixi

.

[ 本帖最后由 御坂美琴 于 2011-1-9 12:23 编辑 ]
收到的鲜花
  • 你们都要疼我哦2011-01-10 01:11 送鲜花  -5朵   附言:忽悠
  • 你们都要疼我哦2011-01-10 01:11 送鲜花  -5朵  
  • 马后炮2011-01-10 12:17 送鲜花  6朵   附言:好文章
  • 马后炮2011-01-10 12:18 送鲜花  6朵   附言:原创内容
  • xufan1232011-01-10 13:14 送鲜花  6朵   附言:好文章
  • xufan1232011-01-10 13:15 送鲜花  6朵   附言:好文章
  • xufan1232011-01-10 13:16 送鲜花  6朵   附言:好文章
  • xufan1232011-01-10 13:16 送鲜花  6朵   附言:好文章
  • xufan1232011-01-10 13:16 送鲜花  6朵   附言:我很赞同
  • xufan1232011-01-10 13:17 送鲜花  6朵   附言:好文章
  • 观弈寒儒2011-01-14 20:28 送鲜花  5朵   附言:好文章
  • 观弈寒儒2011-01-14 20:28 送鲜花  5朵   附言:好文章
  • 观弈寒儒2011-01-14 20:29 送鲜花  5朵   附言:好文章
  • 观弈寒儒2011-01-14 20:29 送鲜花  5朵  
  • 观弈寒儒2011-01-14 20:29 送鲜花  5朵   附言:原创内容
  • 观弈寒儒2011-01-14 20:30 送鲜花  5朵   附言:我很赞同
搜索更多相关主题的帖子: C语言 字符串 艺术 
2011-01-09 11:58
刘定邦
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:687
专家分:1570
注 册:2010-9-21
收藏
得分:3 
先存起来再慢慢学习..
2011-01-09 12:00
a343637412
Rank: 7Rank: 7Rank: 7
来 自:そ ら
等 级:黑侠
帖 子:357
专家分:620
注 册:2010-9-26
收藏
得分:3 
                                            


                                                        来坐沙发的...
2011-01-09 12:04
xufan123
Rank: 5Rank: 5
等 级:职业侠客
帖 子:226
专家分:318
注 册:2010-11-15
收藏
得分:3 
占个地
2011-01-09 12:07
huangapple
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:545
专家分:1790
注 册:2010-12-30
收藏
得分:3 
。太长了

勤能补拙,熟能生巧!
2011-01-09 12:14
qq1023569223
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:湖南科技大学
等 级:贵宾
威 望:26
帖 子:2753
专家分:13404
注 册:2010-12-22
收藏
得分:3 
很好。

   唯实惟新 至诚致志
2011-01-09 12:23
瓦药墙
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:218
专家分:556
注 册:2009-9-16
收藏
得分:3 
顶起那些贴教程的
2011-01-09 12:28
点线面
Rank: 8Rank: 8
来 自:NO.-1
等 级:蝙蝠侠
帖 子:525
专家分:980
注 册:2011-1-3
收藏
得分:1 
LZ的对素数不是理解
就是在所有比1大的整数中,除了1和它本身以外,不再有别的约数,这种整数叫做质数,质数又叫做素数
int isPrime(int n)
{
    int i, s = (int)(sqrt((double)n) + 0.01);  //提示如果不是自定义的,要加#include<math.h>
    if (n <= 3) return 1;        //输入<=1时有问题,1不是素数, 还有输入负数会出错
    if (n % 2 == 0) return 0;    //  建意if( !(n&1)) 这个本身可以判断有没有奇偶性,也判断可是否是2倍数
    for (i = 3; i <= s; i += 2)
        if (n % i == 0)
            break;
    return i > s;
}



[ 本帖最后由 点线面 于 2011-1-9 13:04 编辑 ]

小代码,大智慧
2011-01-09 12:56
w123012306
Rank: 9Rank: 9Rank: 9
来 自:湖南
等 级:蜘蛛侠
威 望:4
帖 子:307
专家分:1180
注 册:2010-4-22
收藏
得分:1 
得瑟一下!

楼上,楼下的一定要幸福开心哦!
2011-01-09 12:57
c语言一手
Rank: 1
等 级:禁止发言
帖 子:20
专家分:0
注 册:2011-1-6
收藏
得分:0 
回复 楼主 御坂美琴
提示: 作者被禁止或删除 内容自动屏蔽
2011-01-09 13:29
快速回复:C语言循环的小艺术(质数判断,菱形打印,奇数阶幻方,字符串循环移位 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017196 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved