第x大的数 汉诺塔系列1 汉诺塔系列2

POOPE

#include<stdio.h>
int a[100010];
int f(int a[],int left,int right,int k)
{
  int i ,j , x;
  x = a[left];
  i = left;
  j = right;
  while(i<j)
  {
    while(i<j&&a[j]<=x)
      j--;
    a[i] = a[j];
    while(i<j&&a[i]>=x)
      i++;
    a[j] = a[i];
  }
  a[i] = x;
  if(i==k)
    return a[k];
  else if(i>k)
    return f(a,left,i-1,k);
    else return f(a,i+1,right,k);
}
int main()
{
  int i , n , m ,t,k;
  while(scanf("%d",&n)!=EOF)
  {
    for(i = 1;i<=n;i++)
      scanf("%d",&a[i]);
     scanf("%d",&t);
     while(t--)
   {
    scanf("%d",&k);
    m = f(a,1,n,k);
    printf("%d\n",m);
   }
  }
  return 0;
}

第X大的数
Problem Description
X最近爱上了区间查询问题，给出N (N <= 100000) 个数，然后进行M (M <= 5) 次询问，每次询问时，输入一个数X (1 <= X <= N)，输出N个数中第X大的数。
Input
多组输入。
每组首先输入一个整数N，代表有N个数，下面一行包含N个整数，用空格隔开。然后为一个整数M，代表有M次询问，下面的M行，每行一个整数X。
Output
输出N个数中第X大的数。
Sample Input
41 2 2 341234
Sample Output
3221
汉诺塔系列1
Problem Description
n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生2^n个系列。由于发生错移产生的系列就增加了，这种错误是放错了柱子，并不会把大盘放到小盘上，即各柱子从下往上的大小仍保持如下关系 ：
n=m+p+q
a1>a2>…>am
b1>b2>…>bp
c1>c2>…>cq
计算所有会产生的系列总数。
Input
Normal07.8 磅02falsefalsefalseMicrosoftInternetExplorer4
包含多组数据，首先输入T,表示有T组数据.每个数据一行，是盘子的数目N<30。
Output
Normal07.8 磅02falsefalsefalseMicrosoftInternetExplorer4
对于每组数据，输出移动过程中所有会产生的系列总数。
Sample Input
31329
Sample Output
32768630377364883

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int  main()
{
  int t;
  scanf("%d", &t);
  while(t--){
    int n;
    scanf("%d", &n);
    long long x;
    x = pow(3,n);
    printf("%lld\n", x);
  }
  return 0;
}

汉诺塔系列2
Problem Description
用1,2,…,n表示n个盘子，称为1号盘，2号盘,…。号数大盘子就大。经典的汉诺塔问
题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于
印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小
顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱
子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。我们
知道最少需要移动2^64-1次.在移动过程中发现，有的圆盘移动次数多，有的少 。 告之盘
子总数和盘号，计算该盘子的移动次数.
Input
包含多组数据，每组首先输入T,表示有T行数据。每行有两个整数，分别表示盘子的数目N(1<=N<=60)和盘号k(1<=k<=N)。
Output
对于每组数据，输出一个数，表示到达目标时k号盘需要的最少移动数。
Sample Input
2
60 1
3 1

#include <stdio.h>
#include <stdlib.h>
  long long int  hannota(int N,int K)
  {
    if(K==N)  return 1;
    else   return hannota(N,K+1)*2;
  }
int main()
{
  int T,N,K,i;
  while(scanf("%d",&T)!=EOF)
  {
    for(i=1;i<=T;i++)
    {
      scanf("%d %d",&N,&K);
      printf("%lld\n",hannota(N,K));
    }
  }
  return 0;
}