C++博客-ACM乐园

文件描述符重定向测试

大大木马 — Tue, 21 May 2013 09:36:00 GMT

这是《Unix环境高级编程》第三章的一道习题，考察文件描述符的重定向问题。为此我写了个测试程序查看上述两条命令的区别。

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>

int main()
{
   write(STDOUT_FILENO,"hello,stdout",sizeof("hello,stdout");
   write(STDERR_FILENO,"hello,stderr",sizeof("hello,stderr");
   return 0;
}

编译为a.out，运行以上两条命令发现：
第一条命令结果是都输出到文件outfile中；第二条命令结果是出错信息输出到控制台，正常信息输出到文件outfile中。

大大木马 2013-05-21 17:36 发表评论

工作分配问题（回溯算法）

大大木马 — Wed, 24 Oct 2012 14:24:00 GMT

问题描述：
设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j] 。试设计一个算法，计算最佳工作分配方案，为每一个人都分配1 件不同的工作，并使总费用达到最小。
数据输入：
第一行一个正整数n(1<=n<=20),接下来的n 行，每行n 个数，表示工作费用。
结果输出:
输出有m行，每行输出最小总费用。
输入样例：
5
50 43 1 58 60
87 22 5 62 71
62 98 97 27 38
56 57 96 73 71
92 36 43 27 95
输出样例：
144

用回溯法求解，这就是在全排列中找出费用最小的

//工作分配问题
/*
3
10 2 3
2 3 4
3 4 5
*/
#include <iostream>
#include
using namespace std;

int table[21][21],n,best,r[21];

int compute(int k)
{
    int temp=0,i;
    for(i=1;i<=k;i++)
        temp+=table[i][r[i]];
    return temp;
}

void search(int k)
{
    if(k==n)
    {
        int temp=compute(n);
        if(temp<best)
            best=temp;
        return;
    }
    for(int i=k;i<=n;i++)
    {
        swap(r[i],r[k]);
        if(compute(k) < best)
            search(k+1);
        swap(r[i],r[k]);
    }
}

int main()
{
    int i,j;
    while(cin>>n,n)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                cin>>table[i][j];
        for(i=1;i<=n;i++)
            r[i]=i;
        best=INT_MAX;
        search(1);
        cout<<best<<endl;
    }
    return 0;
}

大大木马 2012-10-24 22:24 发表评论

网络数据传输问题

大大木马 — Mon, 22 Oct 2012 11:38:00 GMT

问题：有64个有序整数，取值范围为0-255，现将通过64*15只信鸽将这些数据从A地传送到B地，每只信鸽可携带一个整数，取值范围为0-255，由于每只信鸽飞行速度不同，有的先到达，有的后到达，如何给信鸽编码，使得当信鸽到达B地后存在一种方法能识别这些数据的顺序？这些信鸽到达B地后不能再返回A地，并且也不知道哪些鸽子快哪些鸽子慢

大大木马 2012-10-22 19:38 发表评论

会场安排问题（贪心算法）

大大木马 — Fri, 19 Oct 2012 01:38:00 GMT

会场安排问题

问题描述：

　　假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)

编程任务：

　　对于给定的k 个待安排的活动，编程计算使用最少会场的时间表。

数据输入：

　　由文件input.txt 给出输入数据。第一行有1 个正整数k，表示有k 个待安排的活动。接下来的k 行中，每行有2 个正整数，分别表示k 个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。

结果输出:

　　将编程计算出的最少会场数输出到文件output.txt 。

输入文件示例输出文件示例

input.txt output.txt

5 3

1 23

12 28

25 35

27 80

36 50

方法：
1、首先定义数据结构：以时间为核心，定义结构体point，它拥有两个属性，t是时间，f表示是开始时间还是结束时间
2、对所有对象按时间大小排序
3、依次计算，如果是开始时间则count++，如果是结束时间则count--，其中最大的count即是最少的会场数。count表示目前开始且未结束的活动数

//会场安排问题（贪心算法）
//input.txt
//5
//1 23
//12 28
//25 35
//27 80
//36 50
//output.txt
//3
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct point
{
    int t;
    bool f;
};

bool cmp(point x,point y)
{
    return x.t<y.t;
}

int greedy(vector<point> x)
{
    int max=0,cur=0,n=x.size();
    sort(x.begin(),x.end(),cmp);
    for(int i=0;i<n;i++)
    {
        if(x[i].f)
            cur++;
        else
            cur--;
        if((i==n-1 || x[i].t<x[i+1].t) && cur>max)//处理x[i]==x[i+1]的情况
            max=cur;                              //当cur>max且x[i]==x[i+1]时，i时间肯定是开始时间，i+1时间可能是开始时间，也可能是结束时间
    }                                              //如果是结束时间，说明某活动开始时间和结束时间相同，不需要会场，故不对max更新;如果是开始时间，那在i+1次更新max效果一样
    return max;                                   //因此i次不进行更新
}

int main()
{
    vector<point> x;
    int n,i;
    point temp;
    while(cin>>n,n)
    {
        for(i=0;i<n;i++)
        {
            temp.f=true;
            cin>>temp.t;
            x.push_back(temp);
            temp.f=false;
            cin>>temp.t;
            x.push_back(temp);
        }
        cout<<greedy(x)<<endl;
        x.clear();
    }
    return 0;
}

大大木马 2012-10-19 09:38 发表评论

多处最优服务次序问题（贪心算法）

大大木马 — Fri, 19 Oct 2012 00:37:00 GMT

问题描述：
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为t i n i ,1 £ £ 。共有s 处可以
提供此项服务。应如何安排n 个顾客的服务次序才能使平均等待时间达到最小?平均等待时
间是n个顾客等待服务时间的总和除以n。
编程任务：
对于给定的n个顾客需要的服务时间和s的值，编程计算最优服务次序。
数据输入：
由文件input.txt 给出输入数据。第一行有2 个正整数n 和s，表示有n 个顾客且有s处
可以提供顾客需要的服务。接下来的1 行中，有n个正整数，表示n个顾客需要的服务时间。
结果输出:
将编程计算出的最小平均等待时间输出到文件output.txt。
输入文件示例输出文件示例
input.txt output.txt
10 2
56 12 1 99 1000 234 33 55 99 812

输出文件实例

336

贪心策略：最短服务时间优先

//多处最优服务次序问题
//input.txt
//10 2
//56 12 1 99 1000 234 33 55 99 812
//output.txt
//336
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

double greedy(vector<int> x,int s)
{
    vector<int> st(s+1,0);
    vector<int> su(s+1,0);
    int n=x.size();
    sort(x.begin(),x.end());
    int i,j;
    for(i=0;i<n;i++)
    {
        j=i%s;      //第i的任务由第i%s处处理
        st[j]+=x[i];//在第j处处理的任务运行时间之和
        su[j]+=st[j];//在第j处处理的任务等待时间之和
    }
    double t=0;
    for(i=0;i<s;i++)
        t+=su[i];
    t/=n;
    return t;
}

int main()
{
    int n,i,s,a;
    vector<int> x(0);
    while(cin>>n>>s,n&&s)
    {
        for(i=0;i<n;i++)
        {
            cin>>a;
            x.push_back(a);
        }
        cout<<greedy(x,s)<<endl;
        x.clear();
    }
}

大大木马 2012-10-19 08:37 发表评论

金币阵列问题

大大木马 — Fri, 07 Sep 2012 08:09:00 GMT

算法设计与实验题解例题：金币阵列问题
问题描述：
有mxn(m <= 100,n <= 100)个金币在桌面上排成一个m行n 列的金币阵列。每一枚金
币或正面朝上或背面朝上。用数字表示金币状态，0表示金币正面朝上，1 表示背面朝上。
金币阵列游戏的规则是：
（1）每次可将任一行金币翻过来放在原来的位置上；
（2）每次可任选2 列，交换这2 列金币的位置。
算法设计：
给定金币阵列的初始状态和目标状态，计算按金币游戏规则，将金币阵列从初始状态变
换到目标状态所需的最少变换次数。

数据输入：
文件中有多组数据。文件的第1行有1 个正整数k，表示有k 组数据。每组数据的第1 行有2 个正整数m 和n。

以下的m行是金币阵列的初始状态，每行有n 个数字表示该行金币的状态，0 表示金币正面朝上，1 表示背面朝上。

接着的m行是金币阵列的目标状态。

«结果输出:
相应数据无解时输出-1。

输入文件示例
2
4 3
1 0 1
0 0 0
1 1 0
1 0 1
1 0 1
1 1 1
0 1 1
1 0 1
4 3
1 0 1
0 0 0
1 0 0
1 1 1
1 1 0
1 1 1
0 1 1
1 0 1

输入文件示例
2
-1

代码如下：

//最大变换次数不超过m+n
#include <stdio.h>
#include <stdlib.h>

#define swap(a,b) ((a=a+b),(b=a-b),(a=a-b))
int  table1[100][100],table2[100][100],temp[100][100],m,n,ans;//table1为初始状态，table2为目标状态

void cpy(int a[100][100],int b[100][100])//将数组b赋给数组a
{
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            a[i][j]=b[i][j];
}

void change1(int i)//将table1中第i行翻转
{
    for(int j=0;j<n;j++)
        table1[i][j]^=1;
    ans++;
}

void change2(int i,int j)//将table1中第i列与第j列对调
{
    if(i!=j)
    {
        for(int k=0;k<m;k++)
        {
            swap(table1[k][i],table1[k][j]);
        }
        ans++;
    }
}

bool same(int i,int j)//比较table2中第i列与table1中第j列是否相等
{
    for(int k=0;k<m;k++)
        if(table2[k][i]!=table1[k][j])
            return false;
    return true;
}

int main()
{
    int t,i,j,k,best;
    bool flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                scanf("%d",&table1[i][j]);
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                scanf("%d",&table2[i][j]);
        best=m+n+1;
        cpy(temp,table1);//保存初始状态
        for(i=0;i<n;i++) //枚举初始状态每一列变换为目标状态第一列的情况
        {

            ans=0;
            change2(0,i);
            for(j=0;j<m;j++)
                if(table1[j][0]!=table2[j][0])//若此行第一列与目标第一列值不相同，则变换该行
                    change1(j);
            for(j=1;j<n;j++) //在table1中查找与table2中第j列相等的列
            {
                flag=false; //标记是否找到
                for(k=j;k<n;k++)
                    if(same(j,k))
                    {
                        change2(j,k);
                        flag=true;
                        break;
                    }
                if(flag==false)
                    break;
            }
            if(flag && ans<best)
                best=ans;
            cpy(table1,temp);

        }
        if(best<m+n+1)
            printf("%d\n",best);
        else
            printf("-1\n");
    }
    return 0;
}

大大木马 2012-09-07 16:09 发表评论

HDU2147博弈

大大木马 — Sat, 17 Sep 2011 15:17:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=2147
是个博弈的题目，不过通过画图找出它们的规律来效率高。

N N N N .....
P N P N .....
N N N N .....
P N P N .....//p表示失败，N表示成功

#include <iostream>

using namespace std;

int main()
{
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF,m+n)
    {
        if(n&1 && m&1)
            printf("What a pity!\n");
        else
            printf("Wonderful!\n");
    }
    return 0;
}

大大木马 2011-09-17 23:17 发表评论

HDU1398母函数

大大木马 — Sat, 17 Sep 2011 06:58:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=1398

将增量存在数组中，这次有17个表达式相乘。

#include <iostream>

using namespace std;

const int M=301;
int table[18]={
    0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289};//存储第i个表达式的增量
int a[M];
int b[M];

int main()
{
    int i,j,k,n;
    while(scanf("%d",&n)!=EOF,n)
    {
        for(i=0;i<=n;i++)
        {
            a[i]=1;
            b[i]=0;
        }
        for(i=2;i<=17;i++)//17个表达式
        {
            for(j=0;j<=n;j++)
                for(k=0;k+j<=n;k+=table[i])//增量为table[i]
                    b[k+j]+=a[j];
            for(j=0;j<=n;j++)
            {
                a[j]=b[j];
                b[j]=0;
            }
        }
        printf("%d\n",a[n]);
    }
    return 0;
}

大大木马 2011-09-17 14:58 发表评论

HDU1028整数拆分母函数

大大木马 — Sat, 17 Sep 2011 06:22:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=1028

之前用dp做了整数分解，这次学了母函数，用母函数更加方便。理解母函数不难，难在模拟多项式相乘。
首先写成母函数，然后根据该母函数表达式模拟多项式乘法。

//母函数整数拆分
#include <iostream>

using namespace std;

const int M=121;
int a[M]; //存储上一次的系数
int b[M]; //存储这次运算完的系数

int main()
{
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<=n;i++)
        {
            a[i]=1; //保存上一个表达式的系数，作为上一个表达式的系数
            b[i]=0; //保存上一个表达式和这次的表达式相乘后的系数，初始化为0
        }
        for(i=2;i<=n;i++)//这次的表达式是指第i个表达式，上一个表达式是指前i-1个表达式相乘后的最终表达式
                         //第i个表达式的增量为i
        {                //所谓上一个表达式的结构是a0*x^0+a1*x^1+a2*x^2+a3*x^3++aj*x^j++an*x^n
            for(j=0;j<=n;j++)       //j是上一个表达式的指数
                for(k=0;k+j<=n;k+=i)//k是这一次表达式的指数，增量是i
                    b[j+k]+=a[j];   //相乘的过程
            for(j=0;j<=n;j++)
            {
                a[j]=b[j];//将相乘之后的系数，赋给a数组，作为上一次表达式的系数，为下一个循环用（如果还有的话）
                b[j]=0;   //每次都要初始化，为了保存下一次的系数
            }
        }
        printf("%d\n",a[n]);
    }
    return 0;
}

母函数形式：

大大木马 2011-09-17 14:22 发表评论

HDU1102MST

大大木马 — Fri, 16 Sep 2011 07:43:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=1102

#include <iostream>
#include <cmath>

using namespace std;

const int M=27;
const int MAX=10000000;

int map[M][M];
int dis[M]; //存储i节点到当前节点的最短距离
bool visit[M];
int n;
int res; //结果

int min(int a,int b)
{
    return a<b?a:b;
}

void prim(int v)
{
    int i,j,t;
    int min;
    for(i=1;i<=n;i++)
    {
        dis[i]=map[v][i];
        visit[i]=false;
    }
    visit[v]=true;
    res=0;
    for(t=1;t<n;t++) //找点
    {
        min=MAX;
        for(i=1;i<=n;i++)
            if(dis[i]<min && !visit[i]) //找到未访问过的到当前节点最短的点
            {
                min=dis[i];
                j=i;
            }
        if(min==MAX)
            break;
        res+=min;
        visit[j]=true;
        for(i=1;i<=n;i++)            //更新dis数组
            if(map[j][i]<dis[i])
                dis[i]=map[j][i];
    }
}

int main()
{
    int i,j,k,d,t;
    char ch,c;
    while(scanf("%d",&n)!=EOF,n)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=MAX;
        for(t=1;t<n;t++)
        {
            scanf("%c%c",&c,&ch);
            //cin>>ch;
            i=ch-'A'+1;
            scanf("%d",&k);
            while(k--)
            {
                scanf("%c%c",&c,&ch);
                //cin>>ch;
                j=ch-'A'+1;
                scanf("%d",&d);
                map[i][j]=map[j][i]=d;
            }
        }
        prim(1);
        printf("%d\n",res);
    }
    return 0;
}

大大木马 2011-09-16 15:43 发表评论