Tag: 算法

我在哪里可以找到软乘法和除法算法？

我正在研究一种没有硬件乘法和除法的微控制器。 我需要为这些基本操作制作软件算法，这是紧凑尺寸和效率的良好平衡。 我的C编译器端口将使用这些算法，而不是C开发人员自己。 我的google-fu到目前为止主要是关于这个主题的噪音。 谁能指点我的信息？ 我可以使用add / sub和shift指令。 基于表查找的算法也可能对我有用，但我有点担心编译器的后端这么多……嗯，可以这么说。

计算（金钱）从167.37美元变化的不同方式？

这是一个面试问题： 给定金额，比如167.37美元，找到使用货币中可用面额生成此金额变化的所有可能方法？ 任何想到空间和时间有效的算法和支持代码的人，请分享。 这是我写的（工作）代码。 我试图找到这个的运行时间，任何帮助表示赞赏 import java.util.HashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.Map; public class change_generation { /** * @param args */ public static void generatechange(float amount,LinkedList denominations,HashMap useddenominations) { if(amount<0) return; if(amount==0) { Iterator it = useddenominations.keySet().iterator(); while(it.hasNext()) { Float val = it.next(); System.out.println(val +” :: “+useddenominations.get(val)); } System.out.println(“**************************************”); return; } for(Float denom : […]

根据1的数量查找数字的等级

设f（k）= y其中k是非负整数递增序列中的第y个数，其二进制表示中的数目为1，与k相同，例如f（0）= 1，f（1）= 1，f（2）= 2，f（3）= 1，f（4）= 3，f（5）= 2，f（6）= 3，依此类推。 给定k> = 0，计算f（k） 我们很多人都看过这个问题 1这个问题的解决方案是根据1的数量对数字进行分类然后找到rank.i确实找到了一些模式，但这将是一个漫长的过程。 有谁能建议我一个更好的解决方案？

如何处理不适合任何语言数据结构的大整数

我正在尝试解决编程竞赛的初步问题以及我必须计算的两个问题，并打印一些非常大的整数（如100！，2 ^ 100）。 我还需要一种快速的方法来计算这个大整数的幂。 你可以为我建议一些算法或数据结构吗？（顺便说一下，我读过C接口和实现的’任意精度算术’部分，但它对pow（）没有帮助） 编辑：我认为通过平方法和位移的取幂对功率起作用，但我还需要一种快速的方法来计算这个因子的阶乘。 谢谢。 EDIT2：对于那些感兴趣的人; 找到包含长度为N的所有位串的最短位串长度（对不起我的英文，我会给出一个例子）。 N <= 10000 例如，包括长度为2（00,01,10,11）的所有位串的最短位串长度是5（11001）。 我对这个问题的解决方案是2 ^ n + n – 1.（所以我应该计算2的幂，我想我会使用位移） 其他问题是，给定2个长度，找到你可以通过多少种方式达到长度N.例如，输入是10,2,3。那么你应该用2和3达到10（例如，2 + 3） 2 + 2 + 2 + 2,2 + 2 + 3 + 3,3 + 2 + 2 + 3,3 + 3 + 2 + 2 ……）。 1 <= N <2 ^ 63。 […]

图形遍历n步

给出一个简单的无向图，如下所示： 从D，A，B或C（ V_start ）开始 – 我必须计算从n步骤的起始点（ V_start ）到起始点（ V_start ）有多少可能的路径，其中每个边和顶点都可以被访问无限次。 我正在考虑进行深度优先搜索，当steps > n || (steps == n && vertex != V_start)时停止 steps > n || (steps == n && vertex != V_start) ，但是，如果例如n = 1000000 ，则这变得相当昂贵。 我的下一个想法让我将DFS与动态编程相结合，然而，这就是我被困住的地方。 （这不是家庭作业，只是为了学习而被困在图形和算法中。） 如何在合理的时间内用大n解决这个问题？

Peterson的算法对各种优化标志的行为

我想检查gcc和icc的行为以获得各种优化选项。 采用彼得森的2线程互斥算法。 如果交换了lock方法中第a行和第b行（在注释中）的执行顺序，则此算法可能会失败。 使用icc或带有-O0标志的gcc进行编译会产生正确的结果。 使用带有-O3标志的icc进行编译会产生不正确的结果。 使用带有-O3标志的gcc进行编译不会产生任何结果。 程序挂起。 所以我的猜测是-O3标志，gcc和icc都优化了锁定方法，并假设线a和线b之间没有依赖关系。 因此两者产生了错误的结果 这样的依赖很难让编译器找到，所以有没有办法（像ivdep这样的编译器）告诉编译器特定代码块中的依赖关系，这样我们仍然可以在代码的其他部分使用-O3标志 锁定方法： void lock(int me) { int other; other = 1-me; flag[me] = 1; //Line a victim = me; //Line b while(flag[other]==1 && victim == me) { } } 如果交换了行a和行b的执行顺序，则为MUTEX违规的示例： T0 0 sets victim=0 T1 1 sets victim=1 T2 1 sets flag[1]=1 T3 1 checks flag[0]. […]

如何使用单链表实现队列，使其ENQUEUE和DEQUEUE占用O（1）？

这是CLRS 3rd的练习： 10.2-3通过单链表L实现队列。操作ENQUEUE和DEQUEUE仍然需要O（1）时间。 使用单链表实现队列并不困难。 我的问题是关于时间的复杂性。 如何实现带O（1）的ENQUEUE和DEQUEQUE？ 我在谷歌上发现的东西就像使用指针跟踪头部和尾部。 现在问题变成如何使用O（1）时间跟踪单链表上的头尾？ 恕我直言，需要O（n）跟踪尾部。 我对吗？

一种解决电路的算法

我正在自学编程，我想知道如何解决这个问题。 我得到了一组具有给定电阻和给定值的电阻器的电阻器。 我可以选择一定数量的电阻。 如何制作一个尽可能接近电阻的电路？ 程序员告诉我，可以使用遗传算法，但我不限于使用遗传算法。 我想我必须使用基尔霍夫定律制作一个线性方程组来制作方程式，但由于我对电力问题没有太多经验，也没有线性系统的数值算法，所以我想对如何制作这些方法有一些指导随着系统一直在变化，方程式会自动进入计算机内存。 我怎样才能确保算法收敛到更好的解决方案？ 问题来自芬兰的讨论论坛。

NegaMax算法和TicTacToe ……出了什么问题？

我是游戏树算法的新手，我试图实现一个简单的tictactoe游戏，利用NegaMax算法来评估计算机AI玩家的平铺分数。 然而，人工智能行为不是很聪明（我可以一直赢，因为AI不会阻止我的行动），我认为我错误地实施了NegaMax算法。 如果有人可以帮助我使用以下代码，那将是很棒的。 我花了这么长时间尝试不同的东西，但我从来没有让它工作。 #include #include #include #include #include “game_board.h” /** * Constructs a new game board. * * @param size the size of the board (the length of fields) * @return a new GameBoard */ GameBoard* game_board_new(int size) { GameBoard* board = (GameBoard*) calloc(1, sizeof(GameBoard)); board->size = size; board->turn = WHITE; board->fields = (enum […]

简化立方贝塞尔曲线？

我正在尝试使用画笔工具实现与Adobe Illustrator相近的function。 它正确地分析和简化了路径，包括其贝塞尔手柄。 我实施了Ramer-Douglas-Peucker_algorithm，然而，它并没有真正成为我所需要的。 它适用于线段，但不考虑贝塞尔手柄。 是否有算法可以像这个算法一样，但考虑到立方贝塞尔句柄？ 这个问题是曲线可能是一个角度，但算法只能看到一条直线。 谢谢