我们有一个未分类的N个数字序列(1,2,3,4,... N).我们可以通过按特定顺序交换相邻元素来对整个序列进行排序.给定序列,如何计算对序列进行排序所需的最小可能交换.
例如,考虑序列{4,2,5,3,1}.
对此进行排序的最佳方法是按以下顺序使用7次交换
一个贪婪的算法并没有证明是富有成效的.一个反例很容易构建.接近解决方案的下一个明显选择是动态编程.
假设我们有一个未排序的序列:{A1,A2,... Ai,A(i + 1),...,An}.我们知道对序列{Ai,A(i + 1),...,An}进行排序所需的最小交换次数是Min [Ai,A(i + 1),...,An}.问题是找到Min [A(i-1),Ai,...,An].
好吧,我想到的第一个想法就是添加将A(i-1)放在已经排序的序列{Ai,...,An}中的正确位置所需的步骤数.这是有效的:问题中给出的例子已经使用完全相同的方法解决了.
但我无法证明这个解决方案的有效性.这种情况经常发生在我身上.当我认为我已经解决了问题时,我能做的最好的就是获得一个"直观"的证据.我在高中并且没有正确的算法训练.我纯粹出于兴趣而这样做.
是否有严格的数学符号表明这个问题可以转化为正式的证明？这种符号可以扩展到其他问题吗？怎么样？如果能够以高中生可以理解的形式呈现,我将不胜感激.
你必须把一根长棍切成l几块.必须在位置c1, c2, c3, ..., cn处进行切割,其中ci是整数1和n-1(包括)之间的整数.切割的成本等于制作它的棒的长度.削减的顺序应该是什么,以最大限度地降低运营的总成本？
例如,考虑长度10和切割必须在位置进行切割2, 4, 7.你可以按照给定的顺序切割木棒.第一次切割会花费10,因为棒是长度的10.第二次切割会花费8,因为切割所用的剩余棒是长度的10 - 2 = 8.最后的削减将花费6,因为剩余的棍子的长度是10 - 4 = 6.总费用是10 + 8 + 6 = 24
但是,如果我们按顺序切割棒:4, 2, 7我们得到的成本10 + 4 + 6 = 20对我们来说更好.
设计一种算法来解决问题.
我很确定这是一个DP问题.我能看到的一个诱人的复发关系是,如果我们切一根棍子,我们会得到两根小棍子.如果我们知道这两种棒的最佳解决方案,我们可以很容易地找出更大棒的最佳解决方案.但这样效率很低.
如果你有一个递归函数min_cost(stick_length, c_1, c_2, ..., c_n),它返回切割长度stick_length为的最小成本c_1, c_2, ..., c_n,则递归关系看起来像这样
min_cost(stick_length, c_1, …我有一个n x m我需要排序的数组.但是,我只需要查看每个1d数组的第一个值来对较大的数组进行排序.例如,考虑以下2d数组:
[[1, 2], [4, 4], [3, 5]]
我不关心子阵列中的第二个值.我只需要查看子数组的第一个值来对其进行排序.所以,我只会看1, 4, 3.排序,我得到:1, 3, 4.但是整个2d数组看起来应该是这样的:
[[1, 2], [3, 5], [4, 4]]
我尝试使用标准排序算法在c ++中实现它:
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int>& a, vector<int>& b) {
return a[0] < b[0];
}
int main() {
vector< vector<int> > a(3);
//The array I'm building is already sorted. I'm just using it as a test.
for (int i = 0; i < 3; i++) {
vector<int> temp(2, 0); …我想要一个函数,它将为我提供指定长度的所有可能的字符串,这些字符串仅由零和1组成.例如:
spam(4)
应该让我:
['0110', '0111', '0001', '0011', '0010', '0101', '0100', '1110', '1100', '1101', '1010', '1011', '1001', '1000']
我试着用itertools.permutations这份工作.所以,这就是我所做的.
def getPerms(n):
perms = getCandidates(n)
res = []
for i in perms:
res.extend(permutations(i))
res = clean(res)
return res
def clean(ar):
res = []
for i in ar:
temp = ""
for j in i:
temp += j
res.append(temp)
return list(set(res))
def getCandidates(n):
res = []
for i in range(1, n):
res.append("1"*i + "0"*(n-i))
return res
但这非常低效,并在10上输入内存错误.
我正在努力解决这个问题。现在，我能够获得递归解决方案：
如果DP[n]给出以字符串的第n个字符结尾的漂亮的子字符串（在问题中定义）的数量，则要查找DP[n+1]，我们从第（n + 1）个字符向后扫描输入字符串，直到找到第i个字符，使得子字符串从第i个字符开始到第（n + 1）个字符结束都是很漂亮的。如果找不到这样的人，DP[n+1] = 0。
如果这样的字符串被找到，那么，DP[n+1] = 1 + DP[i-1]。
麻烦的是，这种解决方案使一个测试用例超时。我怀疑是向后扫描部分存在问题。我的解决方案的总体时间复杂度似乎为O(N^2)。输入数据的大小似乎表明问题需要O(NlogN)解决。
考虑以下C程序:
int main() {
int a =2;
float b = 2;
float c = 3;
int d = 3;
printf("%d %f %d %f %d %f %d %f\n", a/c, a/c, a/d, a/d, b/c, b/c, b/d, b/d);
printf("%d\n", a/c);
}
这个输出是:
0 0.666667 0 0.666667 2 0.666667 0 0.666667
539648
我根本无法理解这一点.为什么打印a/c为整数给出0,而b/c给出2？在涉及浮点数和整数的计算中,是不是所有整数都被提升为浮点数？所以两种情况下答案都应为0.
在输出的第二行中,我只是将a/c打印为整数,由于某种原因它给出了一个垃圾值(即使它在第一个复合printf语句中打印时它给出了0).为什么会这样？