欧美极品影院,视频一区二区不卡,日韩三区在线观看

Boost Thread學習筆記五

多線程編程中還有一個重要的概念：Thread Local Store（TLS，線程局部存儲），在boost中，TLS也被稱作TSS，Thread Specific Storage。
boost::thread庫為我們提供了一個接口簡單的TLS的面向對象的封裝，以下是tss類的接口定義：

class tss
{
public:
    tss(boost::function1<void, void*>* pcleanup);
    void* get() const;
    void set(void* value);
    void cleanup(void* p);
};

分別用于獲取、設置、清除線程局部存儲變量，這些函數在內部封裝了TlsAlloc、TlsGetValue、TlsSetValue等API操作，將它們封裝成了OO的形式。
但boost將該類信息封裝在detail名字空間內，即不推薦我們使用，當需要使用tss時，我們應該使用另一個使用更加方便的類：thread_specific_ptr，這是一個智能指針類，該類的接口如下：

1 class thread_specific_ptr : private boost::noncopyable   // Exposition only
2 {
3 public:
4   // construct/copy/destruct
5   thread_specific_ptr();
6   thread_specific_ptr(void (*cleanup)(void*));
7   ~thread_specific_ptr();
8
9   // modifier functions
10   T* release();
11   void reset(T* = 0);
12
13   // observer functions
14   T* get() const;
15   T* operator->() const;
16   T& operator*()() const;
17 };

即可支持get、reset、release等操作。
thread_specific_ptr類的實現十分簡單，僅僅為了將tss類“改裝”成智能指針的樣子，該類在其構造函數中會自動創建一個tss對象，而在其析構函數中會調用默認參數的reset函數，從而引起內部被封裝的tss對象被析構，達到“自動”管理內存分配釋放的目的。

以下是一個運用thread_specific_ptr實現TSS的例子：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <boost/thread/tss.hpp>
4 #include <iostream>
5
6 boost::mutex io_mutex;
7 boost::thread_specific_ptr<int> ptr;    // use this method to tell that this member will not shared by all threads
8
9 struct count
10 {
11     count(int id) : id(id) { }
12
13     void operator()()
14     {
15         if (ptr.get() == 0)    // if ptr is not initialized, initialize it
16             ptr.reset(new int(0));    // Attention, we pass a pointer to reset (actually set ptr)
17
18         for (int i = 0; i < 10; ++i)
19         {
20             (*ptr)++;
21             boost::mutex::scoped_lock lock(io_mutex);
22             std::cout << id << ": " << *ptr << std::endl;
23         }
24     }
25
26     int id;
27 };
28
29 int main(int argc, char* argv[])
30 {
31     boost::thread thrd1(count(1));
32     boost::thread thrd2(count(2));
33     thrd1.join();
34     thrd2.join();
35
36     return 0;
37 }

此外，thread庫還提供了一個很有趣的函數，call_once，在tss::init的實現中就用到了該函數。
該函數的聲明如下：
void call_once(void (*func)(), once_flag& flag);
該函數的Windows實現通過創建一個Mutex使所有的線程在嘗試執行該函數時處于等待狀態，直到有一個線程執行完了func函數，該函數的第二個參數表示函數func是否已被執行，該參數往往被初始化成BOOST_ONCE_INIT（即0），如果你將該參數初始化成1，則函數func將不被調用，此時call_once相當于什么也沒干，這在有時候可能是需要的，比如，根據程序處理的結果決定是否需要call_once某函數func。
call_once在執行完函數func后，會將flag修改為1，這樣會導致以后執行call_once的線程（包括等待在Mutex處的線程和剛剛進入call_once的線程）都會跳過執行func的代碼。

需要注意的是，該函數不是一個模板函數，而是一個普通函數，它的第一個參數1是一個函數指針，其類型為void (*)()，而不是跟boost庫的很多其它地方一樣用的是function模板，不過這樣也沒有關系，有了boost::bind這個超級武器，想怎么綁定參數就隨你的便了，根據boost的文檔，要求傳入的函數不能拋出異常，但從實現代碼中好像不是這樣。

以下是一個典型的運用call_once實現一次初始化的例子：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/once.hpp>
3 #include <iostream>
4
5 int i = 0;
6 int j = 0;
7 boost::once_flag flag = BOOST_ONCE_INIT;
8
9 void init()
10 {
11     ++i;
12 }
13
14 void thread()
15 {
16     boost::call_once(&init, flag);
17     ++j;
18 }
19
20 int main(int argc, char* argv[])
21 {
22     boost::thread thrd1(&thread);
23     boost::thread thrd2(&thread);
24     thrd1.join();
25     thrd2.join();
26
27     std::cout << i << std::endl;
28     std::cout << j << std::endl;
29
30     return 0;
31 }

結果顯示，全局變量i僅被執行了一次++操作，而變量j則在兩個線程中均執行了++操作。

posted @ 2008-05-18 18:32 楊磊閱讀(1817) | 評論 (1) | 編輯收藏

Boost Thread學習筆記四

barrier
barrier類的接口定義如下：

1 class barrier : private boost::noncopyable   // Exposition only
2 {
3 public:
4   // construct/copy/destruct
5   barrier(size_t n);
6   ~barrier();
7
8   // waiting
9   bool wait();
10 };

barrier類為我們提供了這樣一種控制線程同步的機制：
前n - 1次調用wait函數將被阻塞，直到第n次調用wait函數，而此后第n + 1次到第2n - 1次調用wait也會被阻塞，直到第2n次調用，依次類推。
barrier::wait的實現十分簡單：

1 barrier::barrier(unsigned int count)
2     : m_threshold(count), m_count(count), m_generation(0)
3 {
4     if (count == 0)
5         throw std::invalid_argument("count cannot be zero.");
6 }
7
8 bool barrier::wait()
9 {
10     boost::mutex::scoped_lock lock(m_mutex);    // m_mutex is the base of barrier and is initilized by it's default constructor.
11     unsigned int gen = m_generation;    // m_generation will be 0 for call 1~n-1, and 1 for n~2n - 1, and so on

12
13     if (--m_count == 0)
14     {
15         m_generation++;    // cause m_generation to be changed in call n/2n/

16         m_count = m_threshold;    // reset count
17         m_cond.notify_all();    // wake up all thread waiting here
18         return true;
19     }
20
21     while (gen == m_generation)    // if m_generation is not changed, lock current thread.
22         m_cond.wait(lock);
23     return false;
24 }

因此，說白了也不過是mutex的一個簡單應用。
以下是一個使用barrier的例子：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/barrier.hpp>
3
4 int i = 0;
5 boost::barrier barr(3);    // call barr.wait 3 * n times will release all threads in waiting
6
7 void thread()
8 {
9     ++i;
10     barr.wait();
11 }
12
13 int main()
14 {
15     boost::thread thrd1(&thread);
16     boost::thread thrd2(&thread);
17     boost::thread thrd3(&thread);
18
19     thrd1.join();
20     thrd2.join();
21     thrd3.join();
22
23     return 0;
24 }

如果去掉其中thrd3相關的代碼，將使得線程1、2一直處于wait狀態，進而使得主線程無法退出。

xtime
xtime是boost::thread中用來表示時間的一個輔助類，它是一個僅包含兩個成員變量的結構體：

1 struct xtime
2 {
3 //

4 xtime_sec_t sec;
5 xtime_nsec_t nsec;
6 };

condition::timed_wait、thread::sleep等涉及超時的函數需要用到xtime。
需要注意的是，xtime表示的不是一個時間間隔，而是一個時間點，因此使用起來很不方便。為了方便使用xtime，boost提供了一些輔助的xtime操作函數，如xtime_get、xtime_cmp等。
以下是一個使用xtime來執行sleep的例子（跟簡單的一句Sleep比起來，實在是太復雜了），其中用到了xtime初始化函數xtime_get：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/xtime.hpp>
3 #include <iostream>
4
5 int main()
6 {
7     boost::xtime xt;
8     boost::xtime_get(&xt, boost::TIME_UTC);    // initialize xt with current time
9     xt.sec += 1;    // change xt to next second
10     boost::thread::sleep(xt);    // do sleep
11
12     std::cout << "1 second sleep over." << std::endl;
13
14     return 0;
15 }

posted @ 2008-05-18 16:48 楊磊閱讀(2111) | 評論 (0) | 編輯收藏

Boost Thread學習筆記三

摘要: 下面先對condition_impl進行簡要分析。 condition_impl在其構造函數中會創建兩個Semaphore（信號量）：m_gate、m_queue，及一個Mutex（互斥體，跟boost::mutex類似，但boost::mutex是基于CriticalSection<臨界區>的）：m_mutex，其中： m_queue 相當于當前所有等待線程的等待隊列，構造函數... 閱讀全文

posted @ 2008-05-18 16:45 楊磊閱讀(1983) | 評論 (1) | 編輯收藏

Boost Thread學習筆記二

除了thread，boost::thread另一個重要組成部分是mutex，以及工作在mutex上的boost::mutex::scoped_lock、condition和barrier，這些都是為實現線程同步提供的。

mutex
boost提供的mutex有6種：
boost::mutex
boost::try_mutex
boost::timed_mutex
boost::recursive_mutex
boost::recursive_try_mutex
boost::recursive_timed_mutex
下面僅對boost::mutex進行分析。
mutex類是一個CriticalSection（臨界區）封裝類，它在構造函數中新建一個臨界區并InitializeCriticalSection，然后用一個成員變量
void* m_mutex;
來保存該臨界區結構。
除此之外，mutex還提供了do_lock、do_unlock等方法，這些方法分別調用EnterCriticalSection、 LeaveCriticalSection來修改成員變量m_mutex（CRITICAL_SECTION結構指針）的狀態，但這些方法都是private的，以防止我們直接對mutex進行鎖操作，所有的鎖操作都必須通過mutex的友元類detail::thread::lock_ops<mutex>來完成，比較有意思的是，lock_ops的所有方法：lock、unlock、trylock等都是static的，如lock_ops<Mutex>::lock的實現：

1 template <typename Mutex>
2 class lock_ops : private noncopyable
3 {
4

5 public:
6     static void lock(Mutex& m)
7     {
8         m.do_lock();
9     }
10

11 }

boost::thread的設計者為什么會這么設計呢？我想大概是：
1、boost::thread的設計者不希望被我們直接操作mutex，改變其狀態，所以mutex的所有方法都是private的（除了構造函數，析構函數）。
2、雖然我們可以通過lock_ops來修改mutex的狀態，如：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <boost/thread/detail/lock.hpp>
4
5 int main()
6 {
7     boost::mutex mt;
8     //mt.do_lock();        // Error! Can not access private member!
9
10     boost::detail::thread::lock_ops<boost::mutex>::lock(mt);
11
12     return 0;
13 }

但是，這是不推薦的，因為mutex、scoped_lock、condition、barrier是一套完整的類系，它們是相互協同工作的，像上面這么操作沒有辦法與后面的幾個類協同工作。
scoped_lock
上面說過，不應該直接用lock_ops來操作mutex對象，那么，應該用什么呢？答案就是scoped_lock。與存在多種mutex一樣，存在多種與mutex對應的scoped_lock：

scoped_lock
scoped_try_lock
scoped_timed_lock

這里我們只討論scoped_lock。
scoped_lock是定義在namespace boost::detail::thread下的，為了方便我們使用（也為了方便設計者），mutex使用了下面的typedef：
typedef detail::thread::scoped_lock<mutex> scoped_lock;
這樣我們就可以通過：
boost::mutex::scoped_lock
來使用scoped_lock類模板了。
由于scoped_lock的作用僅在于對mutex加鎖/解鎖（即使mutex EnterCriticalSection/LeaveCriticalSection），因此，它的接口也很簡單，除了構造函數外，僅有lock/unlock/locked（判斷是否已加鎖），及類型轉換操作符void*，一般我們不需要顯式調用這些方法，因為scoped_lock的構造函數是這樣定義的：

1 explicit scoped_lock(Mutex& mx, bool initially_locked=true)
2 : m_mutex(mx), m_locked(false)
3 {
4 if (initially_locked) lock();
5 }

注：m_mutex是一個mutex的引用。
因此，當我們不指定initially_locked參數構造一個scoped_lock對象時，scoped_lock會自動對所綁定的mutex加鎖，而析構函數會檢查是否加鎖，若已加鎖，則解鎖；當然，有些情況下，我們可能不需要構造時自動加鎖，這樣就需要自己調用lock方法。后面的condition、barrier也會調用scoped_lock的lock、unlock方法來實現部分方法。
正因為scoped_lock具有可在構造時加鎖，析構時解鎖的特性，我們經常會使用局部變量來實現對mutex的獨占訪問。

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <iostream>
4
5 boost::mutex io_mutex;
6
7 void count()    // worker function
8 {
9     for (int i = 0; i < 10; ++i)
10     {
11         boost::mutex::scoped_lock lock(io_mutex);
12         std::cout << i << std::endl;
13     }
14 }
15
16 int main(int argc, char* argv[])
17 {
18     boost::thread thrd1(&count);
19     boost::thread thrd2(&count);
20     thrd1.join();
21     thrd2.join();
22
23     return 0;
24 }

在每次輸出信息時，為了防止整個輸出過程被其它線程打亂，通過對io_mutex加鎖（進入臨界區），從而保證了輸出的正確性。
在使用 scoped_lock時，我們有時候需要使用全局鎖（定義一個全局mutex，當需要獨占訪問全局資源時，以該全局mutex為參數構造一個 scoped_lock對象即可。全局mutex可以是全局變量，也可以是類的靜態方法等），有時候則需要使用對象鎖（將mutex定義成類的成員變量），應該根據需要進行合理選擇。
Java的synchronized可用于對方法加鎖，對代碼段加鎖，對對象加鎖，對類加鎖（仍然是對象級的），這幾種加鎖方式都可以通過上面講的對象鎖來模擬；相反，在Java中實現全局鎖好像有點麻煩，必須將請求封裝到類中，以轉換成上面的四種 synchronized形式之一。

condition
condition的接口如下：

1 class condition : private boost::noncopyable   // Exposition only
2 {
3 public:
4   // construct/copy/destruct
5   condition();
6   ~condition();
7
8   // notification
9   void notify_one();
10   void notify_all();
11
12   // waiting
13   template<typename ScopedLock> void wait(ScopedLock&);
14   template<typename ScopedLock, typename Pred> void wait(ScopedLock&, Pred);
15   template<typename ScopedLock>
16     bool timed_wait(ScopedLock&, const boost::xtime&);
17   template<typename ScopedLock, typename Pred>
18     bool timed_wait(ScopedLock&, Pred);
19 };

其中wait用于等待某個condition的發生，而timed_wait則提供具有超時的wait功能，notify_one用于喚醒一個等待該condition發生的線程，notify_all則用于喚醒所有等待該condition發生的線程。

由于condition的語義相對較為復雜，它的實現也是整個boost::thread庫中最復雜的（對Windows版本而言，對支持pthread的版本而言，由于pthread已經提供了pthread_cond_t，使得condition實現起來也十分簡單），下面對wait和notify_one進行簡要分析。
condition內部包含了一個condition_impl對象，由該對象執行來處理實際的wait、notify_one...等操作。

posted @ 2008-05-18 16:20 楊磊閱讀(5114) | 評論 (1) | 編輯收藏

Boost Thread學習筆記

thread自然是boost::thread庫的主角，但thread類的實現總體上是比較簡單的，前面已經說過，thread只是一個跨平臺的線程封裝庫，其中按照所使用的編譯選項的不同，分別決定使用 Windows線程API還是pthread，或者Macintosh Carbon平臺的thread實現。以下只討論Windows，即使用 BOOST_HAS_WINTHREADS的情況。
thread類提供了兩種構造函數：
thread::thread()
thread::thread(const function0<void>& threadfunc)
第一種構造函數用于調用GetCurrentThread構造一個當前線程的thread對象，第二種則通過傳入一個函數或者一個functor來創建一個新的線程。第二種情況下，thread類在其構造函數中間接調用CreateThread來創建線程，并將線程句柄保存到成員變量m_thread中，并執行傳入的函數，或執行functor的operator ()方法來啟動工作線程。

我們可以用以下三種方式啟動一個新線程：
1、傳遞一個工作函數來構造一個工作線程

2、傳遞一個functor對象來構造一個工作線程

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <iostream>
4
5 boost::mutex io_mutex;
6
7 struct count
8 {
9     count(int id) : id(id) { }
10
11     void operator()()
12     {
13         for (int i = 0; i < 10; ++i)
14         {
15             boost::mutex::scoped_lock lock(io_mutex);        // lock io, will be explained soon.
16             std::cout << id << ": " << i << std::endl;
17         }
18     }
19
20     int id;
21 };
22
23 int main(int argc, char* argv[])
24 {
25     boost::thread thrd1(count(1));
26     boost::thread thrd2(count(2));
27     thrd1.join();
28     thrd2.join();
29     return 0;
30 }
31

3、無需將類設計成一個functor，借助bind來構造functor對象以創建工作線程

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <boost/bind.hpp>
4 #include <iostream>
5
6 boost::mutex io_mutex;
7
8 struct count
9 {
10     static int num;
11     int id;
12
13     count() : id(num++) {}
14
15     int do_count(int n)
16     {
17         for (int i = 0; i < n; ++i)
18         {
19             boost::mutex::scoped_lock lock(io_mutex);
20             std::cout << id << ": " << i << std::endl;
21         }
22         return id;
23     }
24 };
25
26 int count::num = 1;
27
28 int main(int argc, char* argv[])
29 {
30     count c1;
31     boost::thread thrd1(boost::bind(&count::do_count, &c1, 10));
32     thrd1.join();
33     return 0;
34 }

其中bind是一個函數模板，它可以根據后面的實例化參數構造出一個functor來，上面的boost::bind(&count::do_count, &c1, 10)其實等價于返回了一個functor：
struct countFunctor
{
    int operator() ()
    {
        (&c1)->do_count(10);    // just a hint, not actual code
    }
};
因此，以后就跟2中是一樣的了。

posted @ 2008-05-18 14:49 楊磊閱讀(5236) | 評論 (0) | 編輯收藏

ZJU Online Judge 1338

這道題有夠無聊……

看了半天都沒看懂題目是什么，于是直接找了一個能過的代碼

后來發現原來就是找連續的上升，下降的序列的長度的平均數

1 #include <stdio.h>
2
3 int upCount, downCount, pendingCount;
4 int numberOfUpSequences, numberOfDownSequences;
5
6 char state;
7
8 int thisValue, lastValue;
9
10 int main()
11 {
12  float avgUp, avgDown;
13  int done = 0;
14  int count;
15  while ( ! done )
16  {
17   state = 'S';
18   upCount = 0; downCount = 0; pendingCount = 0;
19   count = 0;
20   numberOfUpSequences = 0; numberOfDownSequences = 0;
21   while ( 1 )
22   {
23    scanf("%d", & thisValue);
24    if ( (state == 'S') && (thisValue == 0 ) )
25    {
26     done = 1;
27     break;
28    }
29    else if (thisValue == 0)
30     break;
31    switch ( state )
32     {
33      case 'S':
34      state = 'N';
35       break;
36      case 'N':
37     if ( thisValue == lastValue )
38       pendingCount++;
39     else if ( thisValue < lastValue )
40     {
41      state = 'D';
42      downCount = pendingCount + 1;
43      numberOfDownSequences++;
44     }
45     else if ( thisValue > lastValue )
46     {
47      state = 'U';
48      upCount = pendingCount + 1;
49      numberOfUpSequences++;
50     }
51      break;
52     case 'D':
53     if ( thisValue <= lastValue )
54      downCount++;
55     else if ( thisValue > lastValue )
56     {
57      state = 'U';
58      upCount++;
59      numberOfUpSequences++;
60     }
61      break;
62     case 'U':
63     if( thisValue >= lastValue )
64      upCount++;
65     else if ( thisValue < lastValue )
66     {
67      state = 'D';
68      downCount++;
69      numberOfDownSequences++;
70     }
71      break;
72     }
73    lastValue = thisValue;
74    count++;
75   }
76   if ( state != 'S' )
77   {
78    if ( numberOfUpSequences )
79      avgUp = (float)upCount/numberOfUpSequences;
80    else
81      avgUp = 0.0;
82    if ( numberOfDownSequences )
83      avgDown = (float)downCount/numberOfDownSequences;
84    else
85      avgDown = 0.0;
86    printf("Nr values = %d:  ", count);
87    printf("%f %f\n", avgUp, avgDown );
88   }
89  }
90 }
91
92

posted @ 2008-05-11 17:29 楊磊閱讀(277) | 評論 (0) | 編輯收藏

ZJU Online Judge 1889

又是一個數學問題

一個同余的問題

(a * b + c) % n=[ (a % n) * b + c] % n

呃，看起來都有點像常識了，可是還是不會，大概高中的時候就沒學好

1 #include <iostream>
2
3 using namespace std;
4
5 int main(){
6    int n,rem,digs;
7    while (cin >> n) {
8       for (rem=digs=1;rem%n!=0;digs++) rem = (rem*10+1) % n;
9       printf("%d\n",digs);
10    }
11    return 0;
12 }
13

posted @ 2008-05-10 01:04 楊磊閱讀(228) | 評論 (0) | 編輯收藏

ZJU題型分類

初學者題：
1001 1037 1048 1049 1051 1067 1115 1151 1201 1205 1216 1240 1241 1242 1251 1292 1331 1334 1337 1338 1350 1365 1382 1383 1394 1402 1405 1414 1494 1514 1622 1715 1730 1755 1760 1763 1796 1813 1879 1889 1904 1915 1949 2001 2022 2099 2104 2108 2172 2176 2201 2208 2321 2345 2351 2376 2388 2405 2417 2433

模擬問題：

1006 1009 1012 1016 1019 1023 1026 1028 1038 1042 1045 1051 1056 1057 1058 1061 1065 1066 1068 1072 1073 1078 1087 1088 1097 1098 1099 1103 1111 1121 1124 1126 1128 1133 1138 1146 1152 1154 1160 1175 1178 1187 1194 1207 1222 1224 1244 1259 1267 1274 1275 1277 1278 1279 1281 1282 1294 1295 1300 1308 1317 1324 1339 1351 1362 1392 1393 1397 1398 1399 1400 1402 1432 1434 1444 1452 1475 1487 1493 1497 1517 1526 1527 1530 1531 1552 1569 1573 1592 1601 1610 1623 1631 1641 1652 1657 1659 1682 1692 1700 1702 1707 1708 1712 1728 1732 1737 1746 1747 1750 1752 1754 1758 1764 1768 1774 1797 1799 1804 1807 1811 1822 1824 1831 1834 1837 1838 1842 1844 1845 1854 1858 1862 1870 1881 1884 1889 1896 1906 1921 1951 1969 1978 2000 2022 2040 2046 2047 2051 2072 2084 2101 2112 2131 2133 2138 2148 2153 2156 2160 2164 2172 2178 2184 2185 2187 2189 2193 2196 2201 2204 2208 2211 2212 2220 2229 2233 2239 2240 2261 2262 2269 2277 2288 2301 2309 2311 2312 2316 2320 2321 2322 2328 2330 2350 2389 2405 2410 2414 2420 2421 2483 2508 2560 2569 2572 2593 2613 2617 2680 2681 2731 2732 2743

動態規劃：

1013 1022 1025 1027 1074 1076 1093 1094 1100 1107 1108 1136 1149 1183 1196 1200 1206 1227 1234 1245 1249 1250 1276 1303 1346 1353 1366 1368 1387 1424 1425 1428 1446 1448 1449 1454 1459 1462 1463 1470 1474 1475 1483 1484 1490 1499 1503 1512 1515 1520 1524 1539 1540 1554 1563 1567 1579 1602 1607 1611 1629 1638 1642 1651 1666 1695 1713 1717 1731 1733 1736 1738 1743 1756 1757 1787 1792 1800 1819 1853 1864 1877 1880 1893 1913 1918 1925 1953 1985 1986 1988 1991 1995 2002 2014 2025 2042 2058 2059 2067 2068 2069 2081 2096 2127 2136 2142 2144 2156 2180 2189 2202 2206 2213 2224 2227 2242 2244 2254 2255 2264 2271 2278 2280 2281 2283 2284 2297 2319 2337 2338 2341 2349 2353 2354 2366 2372 2374 2397 2401 2402 2414 2422 2424 2432 2498 2501 2521 2522 2527 2536 2547 2561 2563 2565 2568 2581 2591 2598 2604 2621 2624 2625 2626 2641 2642 2667 2673 2683 2685 2692 2702 2710 2711 2734 2739 2744 2745

字符串處理問題：

1002 1004 1005 1008 1016 1019 1046 1048 1049 1050 1051 1052 1053 1054 1055 1056 1061 1063 1086 1089 1091 1094 1099 1101 1103 1111 1115 1117 1118 1120 1123 1125 1126 1129 1130 1136 1139 1143 1150 1151 1152 1154 1159 1160 1168 1170 1177 1178 1179 1180 1181 1184 1188 1189 1190 1191 1192 1195 1197 1243 1295 1315 1325 1392 1582 1698 1707 1720 1729 1808 1831 1854 1858 1905 1963 1969 1970 1984

搜索問題：

1002 1003 1008 1031 1038 1039 1041 1060 1063 1069 1080 1083 1088 1089 1103 1144 1155 1190 1204 1217 1229 1249 1297 1301 1344 1355 1361 1412 1415 1435 1443 1457 1479 1505 1518 1530 1593 1649 1671 1675 1686 1709 1711 1719 1742 1832 1909 1935 1940 1977 1984 2031 2033 2043 2053 2093 2103 2110 2128 2165 2233 2241 2252 2276 2288 2355 2372 2374 2412 2416 2418 2437 2440 2442 2466 2471 2475 2477 2509 2515 2531 2534 2580 2588 2594 2631 2633 2688

數論問題：

1007 1028 1088 1113 1133 1160 1222 1278 1284 1312 1314 1385 1489 1526 1530 1569 1577 1596 1601 1652 1657 1712 1797 1842 1889 1906 1951 2000 2022 2028 2060 2095 2105 2156 2189 2212 2233 2277 2288 2305 2316 2320 2330 2360 2371 2400 2410 2414

幾何問題：

1010 1032 1037 1041 1081 1090 1104 1123 1139 1165 1199 1426 1439 1460 1472 1597 1608 1648 1683 1910 2015 2102 2107 2157 2228 2234 2318 2335 2347 2352 2361 2370 2375 2394 2403

樹型結構問題：

1011 1038 1043 1062 1141 1159 1167 1203 1319 1335 1387 1406 1481 1511 1542 1586 1610 1635 1674 1700 1752 1788 1805 1809 1900 1944 1955 1959 1965 1990 2243 2425

圖表問題：

1015 1030 1082 1084 1085 1105 1119 1127 1130 1140 1203 1311 1377 1420 1453 1465 1492 1589 1798 1802 1919 1935 2016 2236 2238 2281 2326

匹配問題：

1002 1059 1077 1137 1140 1157 1197 1231 1364 1516 1525 1576 1626 1654 1882 2067 2192 2221 2223 2333 2362 2404

貪心問題：

1025 1029 1076 1117 1161 1239 1360 1543 2049 2091 2109 2315 2343 2425

最短路問題：

1298 1333 1456 1589 1721 1942 1952

博弈問題：1024 1134 1893 1913

最大流問題：1734 1992 2314

其他問題：

1021 1046 1069 1070 1073 1177 1245 1262 1292 1294 1309 1334 1354 1389 1391 1423 1440 1475 1551 1584 1610 1636 1716 1717 1926 1929 1948 1954 1958 1962 1985 1986 1990 2132 2313 2320

posted @ 2008-05-09 16:31 楊磊閱讀(593) | 評論 (0) | 編輯收藏

ZJU Online Judge 1730

呃，數學竟然成了我的弱項，還是我小學奧數沒學明白呢……

很簡單的題目，題意我就不說了

為了完成反向交換，最少的辦法就是從一點把所有人分成兩組

然后每個組進行反向交換，最后加起來就是

如果某一點需要交換到距離自己的距離超過n/2時，那就可以放到另外一組，得到的交換步驟肯定比較少

不知道說清楚了沒有……

代碼在別人那里看到的，最開始自己做的遞推公式錯了……

1 #include<iostream>
2 using namespace std;
3
4 int d(int n)//懂得原理,就是一個算數
5 {
6  int i,t=0;
7  for(i=1;i<n;i++)
8     t+=i;
9  return t;
10 }
11
12 int main()
13 {
14  int n,i,a,p;
15  while(cin>>n)
16  {
17   for(i=0;i<n;i++)
18   {
19    cin>>a;
20    p=d(a/2)+d(a-a/2);//算式
21    cout<<p<<endl;
22   }
23  }
24  return 0;
25 }

posted @ 2008-05-09 16:23 楊磊閱讀(228) | 評論 (0) | 編輯收藏

背包問題

怕忘了，貼上來吧

遞推公式：

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

Sample Code

1 #include<stdio.h>
2 int c[10][100];/*對應每種情況的最大價值*/
3 int knapsack(int m,int n)
4 {
5  int i,j,w[10],p[10];
6  for(i=1;i<n+1;i++)
7         scanf("\n%d,%d",&w[i],&p[i]);
8  for(i=0;i<10;i++)
9       for(j=0;j<100;j++)
10            c[i][j]=0;/*初始化數組*/
11  for(i=1;i<n+1;i++)
12       for(j=1;j<m+1;j++)
13            {
14             if(w[i]<=j) /*如果當前物品的容量小于背包容量*/
15                      {
16                       if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
17
18                            /*如果本物品的價值加上背包剩下的空間能放的物品的價值*/
19
20                          /*大于上一次選擇的最佳方案則更新c[i][j]*/
21                             c[i][j]=p[i]+c[i-1][j-w[i]];
22                             else
23                             c[i][j]=c[i-1][j];
24                      }
25               else c[i][j]=c[i-1][j];
26             }
27  return(c[n][m]);
28
29 }
30 int main()
31 {
32     int m,n;int i,j;
33     scanf("%d,%d",&m,&n);
34     printf("Input each one:\n");
35     printf("%d",knapsack(m,n));
36     printf("\n");/*下面是測試這個數組,可刪除*/
37      for(i=0;i<10;i++)
38       for(j=0;j<15;j++)
39          {
40           printf("%d ",c[i][j]);
41              if(j==14)printf("\n");
42          }
43     system("pause");
44 }
45

posted @ 2008-05-09 15:38 楊磊閱讀(311) | 評論 (0) | 編輯收藏

留言簿(1)

隨筆分類

隨筆檔案

相冊

搜索

最新評論