编程珠玑之第二章:杂耍算法

2024-05-09 15:38

本文主要是介绍编程珠玑之第二章:杂耍算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文系转载链接 http://www.cnblogs.com/solidblog/archive/2012/07/15/2592009.html

作者在文中的证明思路清晰,不过我只看懂了辗转相除法的证明,杂耍的证明未看懂,但是仔细模拟杂耍算法的过程会有比较直接的体会。


问题:将大小为n的数组向左移动i位

基本原理:

     1)先将x[0]移到临时变量t中
    2)将x[i]移动到x[0]中,x[2i]移动到x[i]中,依次类推
    3)将x中的所有下标都对n取模,直到我们又回到从x[0]中提取元素。不过这时我们从t中提取元素,结束。

     移动过程中不会出现数据丢失的问题,即x[i]已经放到正确的位置后,x[i]就是空位,那么后面的x[2i]便可以赋值给x[i]。问题的关键是理解应该执行几次上面的操作,证明的结果是重复执行i和n的最大公约数gcd(i, n)次,在纸上随便写两个正整数,按照上面的过程走一遍,就会发现,这样做事正确的。接下来是链接作者的描述,其中辗转相除的代码有Bug,已经修改,修改策略可以参考《挑战程序设计竞赛》中的2.6.1节。


#include<stdio.h>//使用辗转相除法求最大公约数
int gcd(int a, int b)           //b会不断变小直到0
{if (b == 0)return a;return gcd(b, a%b);         //a与b的最大公约数 == 较大数a与较小数b的余数 (如果一开始a小于b,那么此句会进行交换)
}//杂耍算法
void rotate(char* a,int n,int i)
{int step = gcd(n,i);                    //找到重复执行的次数stepfor(int j = 0; j < step; j++)           //分别以0到step-1作为起点{int temp = a[j];int current = j;while(1){int next= (current + i) % n;if(next== j)                   //如果要提取(向左移动i位)起点值,则退出{break;}a[current] = a[next];          //向左移动i位current= next;}a[current] = temp;                  //将起点的值temp赋给最后空出来的位置(完成向左移动i位的操作)}
}int main()
{char a[9] = "abcdefgh";rotate(a,8,3);printf("%s\n",a);return 0;
}

以下按原文格式转载:

4.辗转相除法求最大公约数

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:

两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

 

我们来看一下这个原理的证明:
设两数为a、b(b<a),用gcd(a,b)表示a,b的最大公约数。
r=a mod b,r为a除以b以后的余数,辗转相除法即是要证明gcd(a,b)=gcd(b,r)。

证明步骤如下:
1)令c=gcd(a,b),则设a=mc,b=nc
2)r = a mod b,所以r = a - k*b = mc - k*nc = (m - kn) * c。即,r = (m - kn) * c
3)由r = (m - kn) * c 可知:c也是r的因数
4)可以肯定m - kn与n互质(why?)
    假设他们不互质,必然存在大于1的整数d,使得m-kn = xd, n = yd。那么,m = xd + kyd = (x + ky)d
    那么,a = mc = (x + ky)dc , b = nc = ydc 。=> a,b的最大公约数为dc,而不是c。
5)既然m - kn与n互质,所以c = gcd(r,b)。
结论,gcd(a,b)=gcd(b,r)

(辗转相除法更详细的描述请参照百度百科:http://baike.baidu.com/view/255668.htm。

5.杂耍算法

杂耍算法中如下两点我无法理解:

1.为什么程序要循环执行gcd(i,n)次
2.这个算法是通过什么样的机制就让所有位置上的元素都移动到了预期的位置

程序的走向我是明白的,但是核心算法始终不得其解。
最终还是需要借助网络,搜到了园子内一位朋友写的文章(关于编程珠玑中习题2.3的一点思考)
看完以后,有种豁然开朗的感觉,在此多谢这个朋友了。

不过,那篇文章中有些概念的细节讲的不是太清楚,我也是借助网络才有了更清晰的了解。
再次,我来总结个精简吧的吧,写的不好还请各位包涵!

先从几个概念开始:

  1. 同余
    如果两个整数(a,b)除以同一个整数m,如果得到相同的余数k。则称a,b对于模m同余。
     记作a ≡ b (mod m)
  2. 同余类
    所谓同余类是指以某一特定的整数(如m)为模,按照同余的方式对全体整数进行的分类。
    对给定的模m,有且恰有m个不同的模m的同余类。它们是:
       0 mod m,1 mod m,…,(m-1)mod m。
  3. 完全剩余类
    通过2)我们知道,所有的整数以m为模可以划分为m个没有交集的集合。
    从每个集合中取一个整数组成一个集合,则这个集合中的m个整数就不存在同余的整数,这个集合就叫做完全剩余类。

了解了以上三个概念后,我们能够得出如下的结论:

如果i和n互质,那么序列:
    0   i mod n     2i mod n    3i mod n    …… (n-1)*i mod n
就包括了集合{0,1,2,……n-1}的所有元素

 

我们为什么会有这样的结论呢,下面来证明一下:
前提条件
    对于模n来说,序列0,1,2,……,n-1本身就是一个完全剩余类(即他们之间两两互不同余)

证明步骤
1)从此序列中任取两个数字xi,xj(0 <= i,j <= n-1),则有Xi≠Xj (mod n),   注:这里由于不能打出不同余字符因此用不等于替代
2)由于i和n是互质的,所以 xi * i ≠ xj * i(mod n)
    =》这就说明,xi从0开始一直取值到n-1,得到的序列0 * i,1 * i,2 *i,……(n-1)*n就是一个完全剩余类。即集合0,1,2,……n-1}

有了以上的结论,如果i和n互质,下面的赋值过程便能完成所有位置的值的移动:
    t = X[0]
    X[0] = X[i mod n]
    X[i mod n] = X[2i mod n]
    …….
    X[(n-2)*i mod n] = X[(n-1)*i mod n]
    X[ (n-1)*i mod n] = t
以上的赋值操作,赋值操作符的两边都得到了一个完全剩余类,也就是说所有的0 ~ n-1的所有位置都被移动过了
请注意第二个操作,X[0] = X[i mod n]。
        该操作决定了整体的导向,该操作将i mod n位置的值移动到了最开始的位置。
        由于i,2i,……之间的偏移量是相同的,所以整个操作实际上就是讲序列向左移动i个位置(超过了开始位置的接到最右边去)


那么如果i和n不互质呢?
自然的想法是利用我们已经得到的结论,让i和n互质,即让i’ = i/(gcd(i,n)),n’ = n/(gcd(i,n))。
这样便构造了一对互质的数, i’和n’。这意味着把整个数组的每g=gcd(i,n)个元素组成块。
由于我们的单位是块元素,每次相当于把g中的一个元素移到最终位置上,所以总共需要g次移动。


这篇关于编程珠玑之第二章:杂耍算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/973795

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言