有暴力强制的麻烦，抛光国旗问题算法？ [英] Having troubles with brute forcing, polish national flag problem algorithm?

问题描述

有一行n>桌子上有1个棋子，其中一些是红色的，有些是白色的。 （红色和白色是波兰国家的颜色。）设计一种算法来重新排列棋子，使所有的红色棋子都在白色棋子之前。唯一允许的操作是检查棋子的颜色和两个棋子的交换。尽量减少算法所产生的掉期数量。



我尝试过：



这项工作但我需要强制它或其他算法。

There is a row of n > 1 checkers on the table, some of them are red and some are white. (Red and white are the colors of the Polish national flag.) Design an algorithm to rearrange the checkers so that all the red checkers precede all the white ones.The only operations allowed are the examination of a checker’s color and the swapping of two checkers.Try to minimize the number of swaps made by your algorithm.

What I have tried:

This work but I need to brute force it,or another algorithm.

entry='ccbbbbcbcbcbbcccb'
list2=list(entry)
print('entrance:'+ entry)
for i in range (0,len(entry)):
    if list2[i]=='c':
        result=''.join(list2)
        print( 'checking %s : %s ' % (i+1 ,result))
        
    else:
        result=''.join(list2)
        print( 'checking %s : %s ' % (i+1 ,result))
        
        for j in range(i+1,len(entry)):
            if list2[j]=='c':

                list2[i],list2[j]=list2[j],list2[i]
                result=''.join(list2)
                print('switch   '+result)
                break
                
print('Solution: '+result)

推荐答案

只是一个提示：可以认为'cc bbbbcbcbcbbccc b'可以缩减为'bbbbcbcbcbbccc'，找到下一步，进一步减少要排序的数据集。

使用一张纸和实验是一个很好的实践来找到算法。



当你不明白你的代码在做什么或为什么它做它做的时候，答案是 debugger 。

使用调试器查看代码正在执行的操作。只需设置断点并查看代码执行情况，调试器允许您逐行执行第1行并在执行时检查变量，这是一个令人难以置信的学习工具。



调试器 - 维基百科，免费的百科全书 [ ^ ]

phpdbg | php调试器 [ ^ ]

PHP程序员的调试技术 [ ^ ]



调试器在这里显示你的代码是什么正在做，你的任务是与它应该做的事情进行比较。

调试器中没有魔法，它没有发现错误，它只是帮助你。当代码没有达到预期的效果时，你就会接近一个错误。

Just an hint: one can consider that 'ccbbbbcbcbcbbcccb' can be reduced to 'bbbbcbcbcbbccc', find the next step to reduce further the data set to sort.
Using a sheet of paper and experimenting is a good practice to find algorithm.

When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute, it is an incredible learning tool.

Debugger - Wikipedia, the free encyclopedia[^]
phpdbg | php debugger[^]
Debugging techniques for PHP programmers[^]

The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.

这篇关于有暴力强制的麻烦，抛光国旗问题算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！