模乘cios算法源码

⑴ 两道编程算法题（两图一道），题目如下，可以给出算法思路或者源代码，源代码最好是C语言的

就会个第一题(因为第一题上已经给出了大致思路)

思路:用map容器(它的内部数据结构是一颗红黑树，查找和插入数据速度非常快)
map<int,st>a;//key(int)：设置为1~n的数;value(st):设置为key的前驱和后继；

这样一来就可以像链表快速插入数据，又可以像数组随机访问元素(key,就相当于数组的下标)

下面是代码和运行截图；

看代码前建议先了解一下map容器的具体用法;

#include<iostream>

#include<map>

#include<vector>

using namespace std;

struct st{//两个成员变量用来储存前驱和后继

int left;//0

int right;//1

st()

{

left=0;

right=0;

}

};

void input(map<int,st> &a)//输出

{

st t;

int s=0;

map<int,st>::iterator it;//迭代器(指针)

for(it=a.begin();it!=a.end();it++)//循环迭代

{

t=it->second;

if(t.left==0)//左边等于0,说明该数是第一个数

{

s=it->first;//记录key

break;

}

}

t=a[s];

cout<<s<<" ";

while(t.right!=0)//循环找当前数的右边的数(右边的为0，就说明该数是最后一个数)

{

cout<<t.right<<" ";

t=a[t.right];

}

}

int main()

{

st t,t_i,t_x,t_k,s;

map<int,st>a;

map<int,st>::iterator it;

int n,x,p,x_l,x_r;

cin>>n;

for(int i=1;i<=n;i++)//map容器赋初值(i,t)

//i:(key)下标;t:(value)结构体变量

{

a.insert(make_pair(i,t));

}

for(int i=2;i<=n;i++)

{

cin>>x>>p;

if(p==0)//x的左边插入i

{

t=a[x];

if(t.left==0)//x的左边没有数

{

t_x.left=i;

t_i.right=x;

a[x]=t_x;

a[i]=t_i;

}

else//x的左边有数

{

int x_left;

t_x=a[x];

x_left=t_x.left;

t_k=a[x_left];

t_i.right=x;

t_i.left=t_x.left;

t_k.right=i;

t_x.left=i;

a[x]=t_x;

a[i]=t_i;

a[x_left]=t_k;

}

}

else//x的右边插入i

{

t=a[x];

if(t.right==0)//x的右边没有数

{

t_x.right=i;

t_i.left=x;

a[x]=t_x;

a[i]=t_i;

}

else//x的左边有数

{

int x_right;

t_x=a[x];

x_right=t_x.right;

t_k=a[x_right];

t_i.left=x;

t_i.right=t_x.right;

t_k.left=i;

t_x.right=i;

a[x]=t_x;

a[i]=t_i;

a[x_right]=t_k;

}

}

}

for(it=a.begin();it!=a.end();it++)//循环迭代打印各个数之间的关系

{

cout<<it->first<<" ";

cout<<"左边:";

cout<<it->second.left<<" ";

cout<<"右边:";

cout<<it->second.right<<endl;

}

input(a);//打印序列

return 0;

}

/*

4

1 0

2 1

1 0

2 3 4 1

*/

⑵ 关于模乘的算法

RSA算法中用到的大数运算

C. 大数的运算
1. 大数的运算原理
RSA算法依赖于大数的运算，目前主流RSA算法都建立在512位到1024位的大数运算之

上，所以我们首先需要掌握大数（比如1024位）的运算原理。
大多数的编译器只能支持到32位（或64位）的整数运算，即我们在运算中所使用的

整数必须小于等于32位，即0xFFFFFFFF，这远远达不到RSA的需要，于是需要专门建

立大数运算库，来解决这一问题。
最简单的办法是将大数当作字符串进行处理，也就是将大数用10进制字符数组进行

表示，然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样

做效率很低。当然其优点是算法符合人们的日常习惯，易于理解。
另一种思路是将大数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行

加减乘除运算，但是这样做代码设计非常复杂，可读性很低，难以理解也难以调试

。
这里我们采用了一种介于两者之间虚腊的思路：将大数看作一个N进制数组，对于目前的

32位系统而言，N可以取2的32次方，即0x100000000，假如将一个1024位的大数转化

成0x10000000进制，它就变成了32位，而每一位的取值范围是0－0xFFFFFFFF。我们

正好可以用一个无符号长整数来表罩侍示这一数值。所以1024位的大数就是一个有32个

元素的unsigned long数组。而且0x100000000进制的数组排列与2进制流对于计算机

来说，实际上是一回事，但是我们完全可以针对unsigned long数组进行“竖式计算

”，而循环规模被降低到物誉吵了32次之内，并且算法很容易理解。
但考虑到乘法和除法，都要进行扩展才能进行快速的计算（如果把除法变减法而不

扩展，速度将慢的无法忍受）。所以我们将N取2的16次方的，即0xFFFF。每一位用

unsigned short来表示，当进行乘除运算时，将short扩展成long，这是编译器所支

持的，所以运算起来，比较快。

⑶ 用C或者C++语言实现这些多精度模乘算法。包括：32bit*32bit，64bit*64bit，128bit*128bit，256bit*256bit

把我的高精度模版 贴一下， 完全可以实现 256bit
。。。。。。。。。。。歼早。。。。氏盯雀。。。。。。。。。。。。。。

#include<iostream>
#include<string>
#include<iomanip>
#include<algorithm>
using namespace std;
class BigNum;
istream& operator>>(istream&, BigNum&);
ostream& operator<<(ostream&, BigNum&);
#define MAXN 9999
#define MAXSIZE 20000 //这是大数的位数，一个数组元素存储四位，那么一共就是20000*4 位数。
#define DLEN 4
class BigNum
{
public:
int a[MAXSIZE]; //数组模拟大数，一个数组元素存储四位数。
int len;
public:
BigNum(){len = 1;memset(a,0,sizeof(a));}
BigNum(const int);
BigNum(const char*);
BigNum(const BigNum &);
BigNum &operator=(const BigNum &);
friend istream& operator>>(istream&, BigNum&);
friend ostream& operator<<(ostream&, BigNum&);
BigNum operator*(const BigNum &) const;

};

//输入重载
istream& operator>>(istream & in, BigNum & b)
{
char ch[MAXSIZE*4];
int i = -1;
memset(b.a,0,sizeof(b.a));
in>>ch;
int l=strlen(ch);
int count=0,sum=0;
for(i=l-1;i>=0;)
{
sum = 0;
int t=1;
for(int j=0;j<4&&i>=0;j++,i--,t*=10)
{
sum+=(ch[i]-'0')*t;
}
b.a[count]=sum;
count++;
}
b.len =count++;
return in;

}

//输出重载则粗。
ostream& operator<<(ostream& out, BigNum& b)
{
int i;
cout << b.a[b.len - 1];
for(i = b.len - 2 ; i >= 0 ; i--)
{
cout.width(DLEN);
cout.fill('0');
cout << b.a[i];
}
return out;
}

//下面是构造函数。
BigNum::BigNum(const int b)
{
int c,d = b;
len = 0;
memset(a,0,sizeof(a));
while(d > MAXN)
{
c = d - (d / (MAXN + 1)) * (MAXN + 1);
d = d / (MAXN + 1); a[len++] = c;
}
a[len++] = d;
}
BigNum::BigNum(const char*s)
{
int t,k,index,l;
memset(a,0,sizeof(a));
l=strlen(s);
len=l/DLEN;
if(l%DLEN)len++;
index=0;
for(int i=l-1;i>=0;i-=DLEN)
{
t=0;k=i-DLEN+1;
if(k<0)k=0;
for(int j=k;j<=i;j++)
t=t*10+s[j]-'0';
a[index++]=t;
}
}
BigNum::BigNum(const BigNum & T) : len(T.len)
{
int i;
memset(a,0,sizeof(a));
for(i = 0 ; i < len ; i++) a[i] = T.a[i];
}
////////////////////////////////////////////////

//赋值重载。
BigNum & BigNum::operator=(const BigNum & n)
{
len = n.len;
memset(a,0,sizeof(a));
for(int i = 0 ; i < len ; i++)
a[i] = n.a[i];
return *this;
}

//乘法重载。
BigNum BigNum::operator*(const BigNum & T) const
{
BigNum ret;
int i,j,up;
int temp,temp1;
for(i = 0 ; i < len ; i++)
{
up = 0;
for(j = 0 ; j < T.len ; j++)
{
temp = a[i] * T.a[j] + ret.a[i + j] + up;
if(temp > MAXN)
{
temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
up = temp / (MAXN + 1);
ret.a[i + j] = temp1;
}
else
{
up = 0;
ret.a[i + j] = temp;
}
}
if(up != 0)
ret.a[i + j] = up;
}
ret.len = i + j;
while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
return ret;
}

/*****************************************/

int main()
{
BigNum a,b,c;
cin>>a>>b; //输入大数。
c=a*b; //计算a*b
cout<<c<<endl; //输出c
return 0;
}

⑷ GitHub 上有哪些完整的 iOS-App 源码值得参考

1. Coding iOS 客户端

Coding官方客户端. 笔者强烈推荐的值得学习的完整APP.
GitHub - Coding/Coding-iOS: Coding iOS 客户端源代码
2. OSCHINA 的 iPhone 客户端
开源中国的iPhone客户端源码
https://git.oschina.net/oschina/iphone-app
3. Git@OSC
Git@OSC iPhone 客户端，方便用户查看Git@OSC的项目以及简单的操作issue等
oschina / git-osc-iphone
4. Firefox for iOS
GitHub - mozilla/firefox-ios: Firefox for iOS
5. zulip-ios
Dropbox收购公司内部社交服务商Zulip,然后全部开源，这是iOS App
GitHub - zulip/zulip-ios: Zulip iOS app
6. iOSSF
SegmentFault官方App
GitHub - gaosboy/iOSSF: SegmentFault官方App
7. iReddit
Reddit iPhone客户端
GitHub - reddit/iReddit: The iReddit iPhone app
8. Monkey
GitHub第三方iOS客户端
GitHub - coderyi/Monkey: Monkey is a GitHub third party client for iOS,to show the rank of coders and repositories.
9. Watch
Dribbble第三方客户端
GitHub - tuesda/Watch: A project which demonstrate how to develop a custom client on android for dribbble.com
10. Voice2Note
懒人笔记iOS客户端
GitHub - liaojinxing/Voice2Note: 懒人笔记iOS客户端
11. RSSRead
“已阅”（iOS上开源RSS新闻阅读器）
GitHub - ming1016/RSSRead: “已阅”（iOS上开源RSS新闻阅读器），有兴趣？那就Pull Requests吧
12. BeeFancy
BeeFancy仿Fancy官方APP的WIREFRAME，基于BeeFramework
GitHub - BeeFramework/BeeFancy: 仿Fancy官方APP的WIREFRAME，基于BeeFramework
13. SXNews
模仿网易新闻做的精仿网易新闻
GitHub - dsxNiubility/SXNews: High imitation Neteasy News. (include list,detail,photoset,weather,feedback)
14. Doppio
寻找最近的星巴克
GitHub - chroman/Doppio: An open source iOS app to find the nearest Starbucks store using NSURLSession, AFNetworking 2.0, Mantle and Starbucks private API.
15. Anypic
类似于Instagram的一款App
GitHub - ParsePlatform/Anypic: An open source mobile and web app that lets users share photos similar to Instagram
16. 豆瓣相册
Slowslab iOS应用 豆瓣相册 精选集 开源项目
GitHub - TonnyTao/DoubanAlbum: Slowslab iOS应用 豆瓣相册 精选集 开源项目，仅供学习参考
17. ChatSecure-iOS
Objective-C写的XMPP聊天应用
GitHub - ChatSecure/ChatSecure-iOS: ChatSecure is a free and open source encrypted chat client for iPhone and Android that supports OTR encryption over XMPP.
18. NotificationChat
Objective-C写的完整的聊天应用
GitHub - relatedcode/EncryptedChat: This is a full native iPhone app to create realtime, text based group or private chat with Parse and Firebase.
19. FakeZhihuDaily
仿知乎日报iOS客户端
GitHub - gnou/FakeZhihuDaily: 仿知乎日报iOS客户端
20. ruby-china-for-ios
RubyChina官方客户端
GitHub - ruby-china/ruby-china-for-ios: Ruby China client for iOS
21. Meizi
豆瓣妹子图iOS客户端
GitHub - Sunnyyoung/Meizi: 豆瓣妹子图iOS客户端
22. PlainReader
一款 iOS(iPhone + iPad) 新闻类客户端，内容抓取自http://cnBeta.com
PlainReader/PlainReader at master · guojiubo/PlainReader · GitHub
23. iOS-2048
用Objective-C实现的2048游戏
GitHub - austinzheng/iOS-2048: iOS drop-in library presenting a 2048-style game
24. ECMobile_iOS
基于ECShop的手机商城客户端
GitHub - GeekZooStudio/ECMobile_iOS: 基于ECShop的手机商城客户端
25. wikipedia-ios
维基网络官方App, 已上架
GitHub - wikimedia/wikipedia-ios: The official Wikipedia iOS app.
26. Sol
漂亮的扁平风格的天气App
GitHub - comyarzaheri/Sol: Sol° beautifully displays weather information so you can plan your day accordingly. Check the weather in your current location or any city around the world. Implemented in Objective-C.