在博客园上看到一个小牛发啦一个剩余算法的分析:
一个婚宴,安排来客,5个人一桌剩余4人,7个人一桌剩6桌,9个人一桌剩余8人,11个人一桌正好,当时看到那个哥们又是剩余算法又是加密算法的,最后抽象出一个算法,如下:
import junit.framework.TestCase;
public class ShareTest1 extends TestCase {
/** *//**
* Return the greatest common divisor.
*/
public static long gcd( long a, long b )
{
if( b == 0 )
return a;
else
return gcd( b, a % b );
}
// Internal variables for fullGcd
private static long x;
private static long y;
/** *//**
* Works back through Euclid's algorithm to find
* x and y such that if gcd(a,b) = 1,
* ax + by = 1.
*/
private static void fullGcd( long a, long b )
{
long x1, y1;
if( b == 0 )
{
x = 1;
y = 0;
}
else
{
fullGcd( b, a % b );
x1 = x; y1 = y;
x = y1;
y = x1 - ( a / b ) * y1;
}
}
/** *//**
* Solve ax == 1 (mod n), assuming gcd( a, n ) = 1.
* @return x.
*/
public static long inverse( long a, long n )
{
fullGcd( a, n );
return x > 0 ? x : x + n;
}
public static long china(long[] n, long[] a) {
// TODO Auto-generated method stub
long n_total = 1L;
final int len = n.length;
for(int i=0;i<len;i++){
n_total *= n[i];
}
long []m = new long[len];
for(int i=0;i<len;i++){
m[i] = n_total / n[i];
}
long []c = new long[len];
for(int i=0;i<len;i++){
c[i] = m[i] * inverse(m[i],n[i]);
}
long a_total = 0L;
for(int i=0;i<len;i++){
a_total += (a[i]*c[i]) % n_total;
}
a_total %= n_total;
return a_total;
}
/** *//**
* @param args
*/
public void test() {
// TODO Auto-generated method stub
long n[] = {5,7,9,11};
long a[] = {4,6,8,0};
//long n[] = {3,5,7};
//long a[] = {2,3,2};
System.out.println(china(n,a));
}
}
我用单元测试一下使用时间:
[img]Finished after 0.005 seconds[/img]
我的算法不会,但是我也是软件工程出生的,略有稍懂,就自己写啦几句实现:
import junit.framework.TestCase;
public class ShareTest extends TestCase{
public void test() {
System.out.println(Long.MAX_VALUE);
for(int i=0;i<Long.MAX_VALUE;i++){
if(i%5==4 && i%7==6 && i%9==8 && i%11==0){
System.out.println("The number is :" + i);
break;
}
}
}
}
我用单元测试一下使用时间:
[img]Finished after 0.005 seconds[/img]
得出的结果竟然惊人的一样,不知道是他分析的算法有问题,还是现在java虚拟机进行拉算法的优化,他在哪撤啦半天的算法,也没有看到效率,哈哈......
分享到:
相关推荐
为实现三维装箱问题的高效求解,提出了一个三维的剩余空间最优化算法(Three-Dimensional Residual-Space-Optimized Algorithm,3D-RSO)。在满足3个著名约束的条件下,该算法将三维问题转化为带有高度约束的二维...
电动汽车剩余里程估计算法开发及验证是电动汽车行业中的一个关键技术,需要通过技术开发和验证来提高电动汽车的续驶里程显示精度和解决用户续驶里程焦虑问题。该技术可以提高电动汽车的普及率和产业发展,并且可以...
剩余类环Zn上圆锥曲线公钥密码体制参数系统的安全性分析及其算法的快速实现,邓从政,,随着计算机技术的迅猛发展,破译传统的公钥密码越来越容易,因此寻找计算密钥困难的新的代数曲线受到了人们的高度关注。...
算法设计与分析 3回溯法—地图填色问题 pre ppt 回溯法地图填色 路径选择(MRV DH) 剪枝策略(向前检测和颜色轮换) 运行时间随图规模增大而增大 图密度 (1) 通过本次实验,我了解到回溯法的基本思想: 不断尝试...
电动汽车剩余续驶里程估算是当前汽车技术领域中的一个关键问题。随着电动汽车的普及,用户对电动汽车的智能化技术体验要求不断提高,车企对剩余里程估算功能越来越重视,对数据准确度要求也越来越高。本文将对电动...
算法将页码数除以 10,得到一个整数商和余数,商就代表页码数减余数外有多少个 1—9 作为个位数,余数代表有 1—余数本身这么多个数作为剩余的个位数,此外,商还代表 1—商本身这些数出现了 10 次,余数还代表剩余...
活动安排问题是一个经典的贪心算法应用场景。假设我们有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的...
算法设计与分析-回溯法地图填色源代码.cpp (1) 回溯法算法设计思想。 (2) 地图填色问题的回溯法解法。 (1) 通过本次实验,我了解到回溯法的基本思想: 不断尝试每一条可行路径,出错时回退,直到找到可行解或全部...
Prim算法是一种贪心算法,它的基本思想是从图中的一个顶点出发,逐步扩展生成树,直到所有顶点都被包含在内。该算法的关键是如何找到连接当前生成树和剩余顶点的最短边来扩充生成树。 为了实现Prim算法,需要使用两...
在每个阶段,我们都作出一个看上去最优的决策,并将其加入到部分解中。如果当前这个输入量的加入,不满足约束条件,则不把此输入加到这部分解中。 二、贪心算法的实现 我们可以使用以下步骤来实现贪心算法: 1. ...
本报告旨在探讨使用 WEKA 中的 DBSCAN 算法对 Wine 数据集进行聚类的效果和分析,为读者提供了一个实用价值的研究报告。 大数据行业分析研究报告 随着数字化和网络化程度的不断加深,我们正在进入一个大数据时代。...
该算法通过AGNES聚类算法对网络进行均匀分簇,然后根据簇内节点的剩余能量和节点与基站距离及两者权重因子,完成分布式簇头选举。接着,采用改进后的Dijkstra算法生成簇头之间的最短路径的多跳路由。 本文首先介绍...
参考C语言版本,用Java写的LL(1)分析总控程序,该语法分析程序实现LL(1)算法的分析过程。分析表是根据已知文法直接在程序中构造的。 本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析,会输出...
在将传统RSA改进为四素数RSA的基础上,再运用数学变换进行参数替换,消除了在公钥中对传输两个随机素数的乘积n的需要,引入了一个新的参数x代替原参数n。针对改进后的算法在运算效率方面的不足,采用中国剩余定理CRT...
贪心算法的设计步骤包括:将最优化问题转化为这样的形式:对其作出一次选择后,只剩下一个子问题需要求解;证明作出贪心选择后,原问题总是存在最优解,即贪心选择总是安全的;证明作出贪心选择后,剩余的子问题满足...
数据结构实验哈夫曼算法实验报告 哈夫曼编码是一种变长前缀编码,用于 lossless 数据压缩。哈夫曼算法是由 David A. Huffman 在 1952 年提出的一种...哈夫曼算法是数据压缩领域中的一个重要算法,具有广泛的应用前景。
本篇论文针对一个新颖,高效的覆盖算法,分析了该算法的设计原理,在此基础上作了改进,并将其实现,对不同情况下该算法所呈现的结果进行了讨论。该算法的特点在于通过一个成本函数来选择覆盖集里的传感器,成本函数...
数据结构设计:首先用一个一维数组表示键盘输入的数,定义一个最大数,设置其初始状态为 0,把连续 4 个数的和用 he 表示,再同 max 进行比较,输出内容就是问题的解。 棋子数的最小值 问题描述:有一堆棋子,2 枚...
(1)请设计一个程序演示死锁避免算法(银行家算法)。 (2)要求该演示程序可以指定任意的进程数量、资源种类、每种资源总数量(大于等于1)、已分配数量、最大需求数量,同时也可以随机生成上述数值进行模拟(随机...
基于节点剩余能量与通信代价的WSNs簇头选择算法方法,姜小荣,唐志博,无线传感器网络(WSNs)是一种以数据处理为中心的无线自组织网络。本文在分析无线传感器网络层次路由协议簇头选择方法的基础上,以延��