From: 合工宣OJ http://xcacm.hfut.edu.cn/problem.php?id=1215
题目描述
有n个人组成的队列，队列中不能有出现女生单独排的情况有多少种？ 例如4个人，可组成以下合法情况 FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM F是女生M是男生 这种情况一共有7种
输入
多组测试数据，每组一个n代表人数(1<=n<=1000)
输出
每组测试数据输出合法情况数。
样例输入
1 2 3
样例输出
1 2 4
本题要首先自己找到递推公式 f[i]=f[i-1]+f[i-2]+f[i-4]; 理解起来很简单，如果最后一个人是女生前面一定还是女生；如果最后一个是男生，前面可能是男生、可能是女生（女生前面还是女生）。这样递推公式就有了。1<=n<=1000，需要用大整数。这道题原先A的时候题目说的不严谨后来才有更正。
代码如下：
1 #include<string> 2 #include<iostream> 3 #include<iosfwd> 4 #include<cmath> 5 #include<cstring> 6 #include<stdlib.h> 7 #include<stdio.h> 8 #include<cstring> 9 #define MAX_L 2005 10 using namespace std; 11 class bign //大整数 12 { 13 public: 14 int len, s[MAX_L]; 15 bign(); 16 bign(const char*); 17 bign(int); 18 bool sign; 19 string toStr() const; 20 friend istream& operator>>(istream &,bign &); 21 friend ostream& operator<<(ostream &,bign &); 22 23 bign operator=(const char*); 24 bign operator=(int); 25 bign operator=(const string); 26 27 bool operator>(const bign &) const; 28 bool operator>=(const bign &) const; 29 bool operator<(const bign &) const; 30 bool operator<=(const bign &) const; 31 bool operator==(const bign &) const; 32 bool operator!=(const bign &) const; 33 34 bign operator+(const bign &) const; 35 bign operator++(); 36 bign operator++(int); 37 bign operator+=(const bign&); 38 bign operator-(const bign &) const; 39 bign operator--(); 40 bign operator--(int); 41 bign operator-=(const bign&); 42 bign operator*(const bign &)const; 43 bign operator*(const int num)const; 44 bign operator*=(const bign&); 45 bign operator/(const bign&)const; 46 bign operator/=(const bign&); 47 48 bign operator%(const bign&)const; 49 bign factorial()const; 50 bign Sqrt()const; 51 bign pow(const bign&)const; 52 53 void clean(); 54 ~bign(); 55 }; 56 #define max(a,b) a>b ? a : b 57 #define min(a,b) a<b ? a : b 58 59 bign::bign() 60 { 61 memset(s, 0, sizeof(s)); 62 len = 1; 63 sign = 1; 64 } 65 66 bign::bign(const char *num) 67 { 68 *this = num; 69 } 70 71 bign::bign(int num) 72 { 73 *this = num; 74 } 75 76 string bign::toStr() const 77 { 78 string res; 79 res = ""; 80 for (int i = 0; i < len; i++) 81 res = (char)(s[i] + '0') + res; 82 if (res == "") 83 res = "0"; 84 if (!sign&&res != "0") 85 res = "-" + res; 86 return res; 87 } 88 89 istream &operator>>(istream &in, bign &num) 90 { 91 string str; 92 in>>str; 93 num=str; 94 return in; 95 } 96 97 ostream &operator<<(ostream &out, bign &num) 98 { 99 out<<num.toStr(); 100 return out; 101 } 102 103 bign bign::operator=(const char *num) 104 { 105 memset(s, 0, sizeof(s)); 106 char a[MAX_L] = ""; 107 if (num[0] != '-') 108 strcpy(a, num); 109 else 110 for (int i = 1; i < strlen(num); i++) 111 a[i - 1] = num[i]; 112 sign = !(num[0] == '-'); 113 len = strlen(a); 114 for (int i = 0; i < strlen(a); i++) 115 s[i] = a[len - i - 1] - 48; 116 return *this; 117 } 118 119 bign bign::operator=(int num) 120 { 121 if (num < 0) 122 sign = 0, num = -num; 123 else 124 sign = 1; 125 char temp[MAX_L]; 126 sprintf(temp, "%d", num); 127 *this = temp; 128 return *this; 129 } 130 131 bign bign::operator=(const string num) 132 { 133 const char *tmp; 134 tmp = num.c_str(); 135 *this = tmp; 136 return *this; 137 } 138 139 bool bign::operator<(const bign &num) const 140 { 141 if (sign^num.sign) 142 return num.sign; 143 if (len != num.len) 144 return len < num.len; 145 for (int i = len - 1; i >= 0; i--) 146 if (s[i] != num.s[i]) 147 return sign ? (s[i] < num.s[i]) : (!(s[i] < num.s[i])); 148 return !sign; 149 } 150 151 bool bign::operator>(const bign&num)const 152 { 153 return num < *this; 154 } 155 156 bool bign::operator<=(const bign&num)const 157 { 158 return !(*this>num); 159 } 160 161 bool bign::operator>=(const bign&num)const 162 { 163 return !(*this<num); 164 } 165 166 bool bign::operator!=(const bign&num)const 167 { 168 return *this > num || *this < num; 169 } 170 171 bool bign::operator==(const bign&num)const 172 { 173 return !(num != *this); 174 } 175 176 bign bign::operator+(const bign &num) const 177 { 178 if (sign^num.sign) 179 { 180 bign tmp = sign ? num : *this; 181 tmp.sign = 1; 182 return sign ? *this - tmp : num - tmp; 183 } 184 bign result; 185 result.len = 0; 186 int temp = 0; 187 for (int i = 0; temp || i < (max(len, num.len)); i++) 188 { 189 int t = s[i] + num.s[i] + temp; 190 result.s[result.len++] = t % 10; 191 temp = t / 10; 192 } 193 result.sign = sign; 194 return result; 195 } 196 197 bign bign::operator++() 198 { 199 *this = *this + 1; 200 return *this; 201 } 202 203 bign bign::operator++(int) 204 { 205 bign old = *this; 206 ++(*this); 207 return old; 208 } 209 210 bign bign::operator+=(const bign &num) 211 { 212 *this = *this + num; 213 return *this; 214 } 215 216 bign bign::operator-(const bign &num) const 217 { 218 bign b=num,a=*this; 219 if (!num.sign && !sign) 220 { 221 b.sign=1; 222 a.sign=1; 223 return b-a; 224 } 225 if (!b.sign) 226 { 227 b.sign=1; 228 return a+b; 229 } 230 if (!a.sign) 231 { 232 a.sign=1; 233 b=bign(0)-(a+b); 234 return b; 235 } 236 if (a<b) 237 { 238 bign c=(b-a); 239 c.sign=false; 240 return c; 241 } 242 bign result; 243 result.len = 0; 244 for (int i = 0, g = 0; i < a.len; i++) 245 { 246 int x = a.s[i] - g; 247 if (i < b.len) x -= b.s[i]; 248 if (x >= 0) g = 0; 249 else 250 { 251 g = 1; 252 x += 10; 253 } 254 result.s[result.len++] = x; 255 } 256 result.clean(); 257 return result; 258 } 259 260 bign bign::operator * (const bign &num)const 261 { 262 bign result; 263 result.len = len + num.len; 264 265 for (int i = 0; i < len; i++) 266 for (int j = 0; j < num.len; j++) 267 result.s[i + j] += s[i] * num.s[j]; 268 269 for (int i = 0; i < result.len; i++) 270 { 271 result.s[i + 1] += result.s[i] / 10; 272 result.s[i] %= 10; 273 } 274 result.clean(); 275 result.sign = !(sign^num.sign); 276 return result; 277 } 278 279 bign bign::operator*(const int num)const 280 { 281 bign x = num; 282 bign z = *this; 283 return x*z; 284 } 285 bign bign::operator*=(const bign&num) 286 { 287 *this = *this * num; 288 return *this; 289 } 290 291 bign bign::operator /(const bign&num)const 292 { 293 bign ans; 294 ans.len = len - num.len + 1; 295 if (ans.len < 0) 296 { 297 ans.len = 1; 298 return ans; 299 } 300 301 bign divisor = *this, divid = num; 302 divisor.sign = divid.sign = 1; 303 int k = ans.len - 1; 304 int j = len - 1; 305 while (k >= 0) 306 { 307 while (divisor.s[j] == 0) j--; 308 if (k > j) k = j; 309 char z[MAX_L]; 310 memset(z, 0, sizeof(z)); 311 for (int i = j; i >= k; i--) 312 z[j - i] = divisor.s[i] + '0'; 313 bign dividend = z; 314 if (dividend < divid) { k--; continue; } 315 int key = 0; 316 while (divid*key <= dividend) key++; 317 key--; 318 ans.s[k] = key; 319 bign temp = divid*key; 320 for (int i = 0; i < k; i++) 321 temp = temp * 10; 322 divisor = divisor - temp; 323 k--; 324 } 325 ans.clean(); 326 ans.sign = !(sign^num.sign); 327 return ans; 328 } 329 330 bign bign::operator/=(const bign&num) 331 { 332 *this = *this / num; 333 return *this; 334 } 335 336 bign bign::operator%(const bign& num)const 337 { 338 bign a = *this, b = num; 339 a.sign = b.sign = 1; 340 bign result, temp = a / b*b; 341 result = a - temp; 342 result.sign = sign; 343 return result; 344 } 345 346 bign bign::pow(const bign& num)const 347 { 348 bign result = 1; 349 for (bign i = 0; i < num; i++) 350 result = result*(*this); 351 return result; 352 } 353 354 bign bign::factorial()const 355 { 356 bign result = 1; 357 for (bign i = 1; i <= *this; i++) 358 result *= i; 359 return result; 360 } 361 362 void bign::clean() 363 { 364 if (len == 0) len++; 365 while (len > 1 && s[len - 1] == ' ') 366 len--; 367 } 368 369 bign bign::Sqrt()const 370 { 371 if(*this<0)return -1; 372 if(*this<=1)return *this; 373 bign l=0,r=*this,mid; 374 while(r-l>1) 375 { 376 mid=(l+r)/2; 377 if(mid*mid>*this) 378 r=mid; 379 else 380 l=mid; 381 } 382 return l; 383 } 384 385 bign::~bign() {} 386 387 bign f[MAX_L]; 388 389 int main() //主函数 390 { 391 int a,i; 392 f[0]=1;f[1]=1;f[2]=2;f[3]=4; 393 for(i=4;i<=1000;i++) 394 { 395 f[i]=f[i-1]+f[i-2]+f[i-4]; 396 } 397 while(cin>>a) 398 { 399 cout<<f[a]<<endl; 400 } 401 return 0; 402 } 403 /************************************************************** 404 Problem: 1215 405 User: 2014217052 406 Language: C++ 407 Result: 正确 408 Time:58 ms 409 Memory:17232 kb 410 ****************************************************************/