无界 - BlogJava

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 杨磊阅读(1823) | 评论 (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 杨磊阅读(2115) | 评论 (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 杨磊阅读(1991) | 评论 (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 杨磊阅读(5121) | 评论 (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 杨磊阅读(5243) | 评论 (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 杨磊阅读(286) | 评论 (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 杨磊阅读(236) | 评论 (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 杨磊阅读(600) | 评论 (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 杨磊阅读(237) | 评论 (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 杨磊阅读(318) | 评论 (0) | 编辑收藏

留言簿(1)

随笔分类

随笔档案

相册

搜索

最新评论