摘要: 了解C++的童鞋都知道algorithm里面有個next_permutation可以求下一個排列數，通過《STL 源碼剖析》（或者自己讀代碼）可以知道其實現，比如：
abcd next_permutation -> abdc
那么，為什么abcd的下一個是abdc而不是acbd呢？
閱讀全文
posted @
2010-02-24 00:11 尹東斐 閱讀(3454) |
評論 (7) |
編輯 收藏
條件：1K內存，1MHzCPU，每秒可以改變2^20次狀態。問：一個程序最長的運行時間是多少？
答： 首先程序是確定性的，就說明內存的狀態不會重復，否則就永遠結束不了。從這一點出發，可以知道內存的狀態共有 2^8k , 然后CPU每秒改變 2^20 個狀態，所以這臺計算機最長出現不重復的狀態 2^(8k-20）秒。 |
posted @
2009-10-15 10:57 尹東斐 閱讀(3708) |
評論 (12) |
編輯 收藏
題目描述：設有n個正整數，將它們聯接成一排，組成一個最小的多位整數。
程序輸入：n個數程序輸出：聯接成的多位數
例如：n=2時，2個整數32，321連接成的最小整數為：32132，n=4時，4個整數55，31，312, 33 聯接成的最小整數為：312313355
[題目要求]1. 給出偽代碼即可，請給出對應的文字說明，并使用上面給出的例子試驗你的算法。2. 給出算法的時間空間復雜度。3. 證明你的算法。（非常重要）
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <iostream>
#include <iterator>
#include <sstream>
using namespace std;
struct Less
{
bool operator()(long i, long j)
{
static stringstream ss;
ss.clear();
ss<<i<<" "<<j;
string stri,strj;
ss>>stri>>strj;
return (i*powl(10,strj.length())+j) < (j*powl(10,stri.length()) +i);
}
};
int main()
{
long x[] = {565, 56, 5655};
sort(x, x+3, Less());
copy(x, x+3, ostream_iterator<long>(cout));
}證明：
假設： 排序后的 a0a1...an不是最小的，那么存在a0a1...ajai....an<a0a1...an,且ajai > aiaj.
那么交換ajai會使可以使a0a1...an更小，與假設a0a1...ajai....an<a0a1...an矛盾。
證明完畢。
posted @
2009-06-04 23:49 尹東斐 閱讀(729) |
評論 (2) |
編輯 收藏
摘要: 這一塊主要是講move語義的，我認為這是在C++0x中，最好的特性之一，因為它幾乎可以完全透明的提高效率。在Stephan T. Lavavej這篇帖子之后，有很多評論，大體上認為C++因為這些特性而變得更復雜了，而難以掌握，另初學者望而生畏。但是我認為這是值得的，因為C++的宗旨是：“don't pay for what you don't use 不要為你不使用的東西而付出代價&#...
閱讀全文
posted @
2009-05-28 20:51 尹東斐 閱讀(1613) |
評論 (0) |
編輯 收藏
摘要:
最近最大的新聞莫過于微軟發布Visual Studio2010了，對c++的支持更進一步，其intellsence的解析也使用了和以前完全不同的方法（以前是靠編譯器，現在是獨立inellsence單元），番茄可能要被打入冷宮了。Stephan T. Lavavej在Visual c++ Team Blog上發布了VC10對C++0x標準的支持情況，包括：lambdas, auto，...
閱讀全文
posted @
2009-05-27 23:17 尹東斐 閱讀(1867) |
評論 (3) |
編輯 收藏
最近項目里總是要對很龐大的公式求導，很煩人，手工求導容易出錯。
當然MATLAB是個好選擇，不過當它要錢的時候，您可能就不這么認為了。
于是，實現了一個可以
編譯期求導(不用擔心運行時負擔)的小型庫，還不完全，僅支持多項式，sin，cos，pow，exp，log等函數求導。
后期的表達式優化做的不是很好。
下面是一些測試代碼，完整的源碼在
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=[math]AD.zip實現部分很復雜，請多多指教。
只有1個函數， d(...)
支持高階，多元求導。
d(exp, var)(value1, value2, ...)
exp內可以有多個變量，var表示要對其求導的變量，value表示求導以后用于計算表達式的變量的值。
比如:
d(d(x*x*x, x),x)(3.0) 表示對x*x*x求二階導數在x=3.0時候的值。
d(d(x*x*y, x), y)(3.0, 4.0) 表示d(x*x*y)/(dxdy)在x=3.0，y=4.0的值。
d(d(x*x*x, x) +d(y*x, y), y) (2.0) 則表示 (d(x*x*x)/dx + d(y*x)/dy)/dy == 0。
可以直接用cout把求導后的表達式輸出，不用給變量給值。
cout<<d(x*x, x) // 結果是：2*x
這里沒有用任何迭代，是直接對表達式求導的。返回值是求導后的表達式，本質是一個仿函數。可以用boost::function保存起來使用。
例如：
boost::function<double (double)> df = d(pow(x, const_<10>::type()), x); //df 參數為1個double，返回double
然后就可以在任何地方使用 df 了：
double res = df(3.0) // res == pow(3, 9)
1#include "ad.h"
2#include <iostream>
3#include <iterator>
4
5using namespace std;
6
7int main()
8{
9 variable<0>::type x;
10 variable<1>::type y;
11
12 double res[14];
13
14 res[0] = d(pow(x, const_<10>::type()), x)(2.0);
15
16 res[1] = d(x * x * x, x)(2.0);
17 res[2] = d(x + x + x, x)(2.0);
18 res[3] = d(x - x - x, x)(2.0);
19 res[4] = d(x / x, x)(2.0);
20
21 res[5] = d(pow(x, var(3.0)), x)(2.0);
22 res[6] = d(pow(var(3.0), x), x)(2.0);
23 res[7] = d(pow(x, x), x)(2.0);
24
25 res[8] = d(log(x), x)(2.0);
26 res[9] = d(exp(x), x)(2.0);
27
28 res[10] = d(sin(x), x)(2.0);
29 res[11] = d(cos(x), x)(2.0);
30
31 res[12] = d(d(sin(x) * cos(y), x), y)(2.0, 3.0);
32
33 res[13] = (d(log(x) + x, x) * x)(2.0);
34
35 copy(res, res + 14, ostream_iterator<double>(cout, "\n"));
36
37 cout<<d(pow(x, const_<10>::type()), x)<<endl;
38
39 cout<<d(x * x * x, x)<<endl;
40 cout<<d(x + x + x, x)<<endl;
41 cout<<d(x - x - x, x)<<endl;
42 cout<<d(x / x / x, x)<<endl;
43
44 cout<<d(pow(x, var(3.0)), x)<<endl;
45 cout<<d(pow(var(3.0), x), x)<<endl;
46 cout<<d(pow(x, x), x)<<endl;
47
48 cout<<d(log(x), x)<<endl;
49 cout<<d(exp(x), x)<<endl;
50
51 cout<<d(sin(x), x)<<endl;
52 cout<<d(cos(x), x)<<endl;
53
54 cout<<d(d(sin(x) * cos(y), x), y)<<endl;
55
56 cout<<(d(log(x) + x, x) * x)<<endl;
57
58 return 0;
59}
60
輸出結果如下：
1512
212
33
4-1
50
612
79.88751
86.77259
90.5
107.38906
11-0.416147
120.909297
13-0.0587266
143
15pow(x,9)
16(((x+x)*x)+(x*x))
173
18-1
19(-1/(x*x))
20(pow(x,3)*(3*(1/x)))
21(pow(3,x)*log(3))
22(pow(x,x)*(log(x)+1))
23(1/x)
24exp(x)
25cos(x)
26sin(x)
27(cos(x)*sin(y))
28(((1/x)+1)*x)
29
posted @
2009-05-01 23:50 尹東斐 閱讀(2624) |
評論 (6) |
編輯 收藏