[算法]出个题目给大伙儿做得了

rainbow-X

2. #include<iostream>
4. void move(int a[], int n, int k)
5. {
6.     int i = (0+k)%n;
7.     int tmp;   
8.     while(i != 0) {
9.         //swap(a[0], a[i]);
10.         tmp            = a[0];
11.         a[0]            = a[i];
12.         a[i]        = tmp;
13.        
14.         i = (i+k)%n;
15.     }
16. }
18. int main()
19. {
20.     int a[10] = {0,1,2,3,4,5,6,7,8,9};
22.     std::cout <<"a[10]=";
23.     for(int i = 0; i < 10; i++)
24.         std::cout << a[i] << " ";
25.     std::cout << std::endl;
27.     move(a, 10, 3);
29.     std::cout <<"a[10]=";
30.     for(int i = 0; i < 10; i++)
31.         std::cout << a[i] << " ";
32.     std::cout << std::endl;
33. }

复制代码

应该符合题目要求了，只用了move函数中只用了i和tmp两个辅助变量。时间复杂度为O(n).

longfei_007

使用链表数据结构不就可以了！干什么搞那么麻烦？

ideawu

问大家个问题，CPU执行加，减，乘，除，取模，内存移动所需的时钟周期大概是多少。比如用Pentium3来讨论。

ideawu

我的做法：
***
是O(n^2)了。再想想。
放弃。
记住light_zls提到的做法。

vestige

要知道每条指令需要多少指令周期，需要知道一条指令由多少条微程序构成，intel公司应该不会公布这么地层东西吧？ 如果就MIPS来说的话，加减操作指令周期是固定的，其数量取决于流水线的长度，但乘除法的指令周期于操作数的长度也有很大关系，x86估计也差不多是这样，所以要知道上述指令的指令周期数应该比较困难吧。。。

ideawu

Post by vestige
要知道每条指令需要多少指令周期，需要知道一条指令由多少条微程序构成，intel公司应该不会公布这么地层东西吧？ 如果就MIPS来说的话，加减操作指令周期是固定的，其数量取决于流水线的长度，但乘除法的指令周期于操作数的长度也有很大关系，x86估计也差不多是这样，所以要知道上述指令的指令周期数应该比较困难吧。。。

我明天去图书馆找找，看过的。

longfei_007

回去找本计算机组成原理就有。
保证上面有明确的答案

hlt0430

除非你又跟踪软件，否则你无法知道多长时间？？而且你的问题又冲突啊！内存的多少与内存移动时的消耗时间怎么来计算？现在只有参与硬件设计的人知道了。

ideawu

有一本清华大学出版社的书（《80x86 IBM PC及兼容计算机 卷一和卷二 汇编语言、设计与接口技术》(美) Muhammad Ali Mazidi, Janice Gillispie Mazidi著 清华大学出版社 2004），里面有指令运行周期的对比，不一定准确，仅供参考：
对于486,
加法指令ADD，1个时钟周期
除法指令DIV，41个时钟周期