金额问题

如您所知，在著名的硬币任务中，需要计算零钱，这有两个麻烦 。
-第一个是硬币的面额数量，
-第二个是代表更改的位数。
而且这两个量都对图灵机的负载产生指数影响，而图灵机的负载实际上是在计算中。
即使在酗酒者社会中，一次认识到一个人同时具有两个依赖性也不能被接受。 因此，我决定放心使用它，并提前消除这些问题之一。 这将是硬币面额的数量。

简而言之， 问题的实质描述如下：指数依赖性。 也就是说，发行不存在面额的新型硬币将使硬币组合的数量增加一倍。 另一个面额-两倍，以此类推，直到条件无穷大。 随着通货膨胀的加剧，当经常发行新硬币/钞票时，您将不得不购买功能更强大的计算机来解决该问题。 在通货膨胀率高的通货膨胀中从哪里得到钱呢？

因此，一个实际上很简单的解决方案 。
如果您想象一个从零到C（变化）的线段，其上的点对应于硬币的面额，那么任何有识之士都会大致看到以下图片：

好吧，也许是不同的颜色。
那么，关于红点我们能说些什么呢？ 当然，与这一点相对应的数字就是我们可以以变化形式给出的数量。 一枚硬币。 也许有人看到了别的东西，但是作为一名艺术家，我恰恰投入了这种意义。 而且，作为一名艺术家，我将在这张图片中绘制另一个点，该点与第一个点（从左到右）的总和相同，且点相同（一切正确：它将使面值翻倍）。 我用相同的颜色绘制，因为一个新的点表示相同的东西-这个数量也可以改变。

接下来，即使第二点是先前的金额，我也将第一点与第二点进行总结（这无关紧要，因为此处所有点均相等）。 我将再次在细分市场上提出新的观点。

如果新点超出了线段的边界，则我们不会画任何东西，而是返回到线段的起点，并获取下一个点，即第二个点。 进一步相同（从左到右）。
实际上，当C点（我提醒您，这是变化）变成红色时，我们可以假定已找到解决方案。 而且，您可以经历整个周期并找到最佳解决方案，以使硬币数量最少。

从编程的角度来看，有两个循环。 第一个是从0到C / 2（无需取较大C / 2的第一个点，因为第二个点始终大于第一个点，并且总的来说它们将超出段的边界）。 第二个循环内置在第一个循环中，它从外部循环指向的同一点开始，直到总和离开该段的边界。
实际上，这是一个破产：我们不会失去一个选择，我们可以保证找到最佳解决方案，否则我们将得出结论，没有解决方案。

让我们计算一下循环中的迭代量 。 在外部循环中，它是C / 2，在内部循环中，它几乎是相同的。 乘以C / 2 * C / 2 =（C ^ 2）/4。四舍五入到C的平方。 当我们整个细分市场仅由红点组成时，这是最糟糕的选择。 如果这些点之间有空格，则迭代次数将大大减少。
如您所见，在确定解决问题的难度时，我们不使用硬币面额的数量。 该值不会直接影响解决方案的复杂性。 这些面额的价值会影响1分硬币，使此部分完全变成红色。 因此，最好不要考虑此硬币，并且在决策结束时，请选择最接近C的红点，并在1美分的顶部绘制草图。 但是，这已经是算法优化的时刻了，这超出了本文的范围。

实际上，我想说的就是这些。 该程序的工作版本可以在这里找到： github链接

1.在init.h文件中，设置COINS_NUMBER（硬币的面额数量）和AMOUNT（零钱）。
2.在文件coinc.c中，在coins数组中指定硬币的面额。
3.在Linux下，运行make_sh。
4.运行应用程序以执行


让我给你举个有趣的例子 。 想象一下，在某个国家，数学家上台并发行了32种面额的硬币：2、3、5、7、11、13、17、19 ...131。为了方便计数，只选择了质数（嗯，这很有趣吗？ ？）。 为了确保货币改革成功，他们在信使的商店里派了一个信使来交换账单5333（也是质数）。 使用一种旧的单核解决方案的收银员解决了该问题：39个硬币的面值为131 Pythagoras，一个硬币127和一个97。计算花费了3秒的时间，并且只占用了一个兆字节的内存。 他相信政府很快得知人们对改革感到满意。


还有一个更难以验证的示例 。 硬币，面额为100，面值如此奇怪：0101、0202、0303 ... 9898、9999、100100。零钱数额：101010。寻找解决方案需要1秒钟，仅比一兆字节的内存多一点。 但是，实际上并不是这样的决定，即不可能用这样的硬币来收集这么多的钱。 使用相同的硬币，一百万张支票将花费26兆字节和几百秒，这表明硬币数量而不是币种数量成指数关系。