第34次编程比赛题目（第1题）

主题：第34次编程比赛题目（第1题）

eastcowboy [专家分：25370] 发布于 2006-07-07 12:13:00

题目描述：
某实验室的管理员管理着一跟[color=0000FF]长为1米的电线[/color]。做实验的人可以从他那里借走或是还回电线。该管理员采用了以下的管理办法：
1、将开始时的电线放在柜子里。
2、当有人要还回电线时，把还来的电线放到柜子里。
3、当有人要借走电线时，在柜子里找到长度大于等于借者所要求长度的所有电线，从中选出长度最短的一根，然后剪下借者需要的长度，将剪下的部分借出。如果有剩下的部分，将它放到柜子里。如果借电线时柜子里没有可以满足要求的电线，则无法借出。

请根据以上规则编写四个函数，对管理过程进行模拟：
void Start(void);          /* 保证只在实验开始时调用一次 */
void In(int length);       /* 实验开始后、实验结束前可能调用多次 */
int  Out(int length);      /* 实验开始后、实验结束前可能调用多次 */
void End(void);            /* 保证只在实验结束时调用一次 */
四个函数的功能介绍：
Start函数：用于初始化。
End函数：  用于处理释放内存等善后工作，如果不需要善后，此函数中可以没有任何代码。
In函数：   用于处理还回电线，其中参数length表示了还回的长度，[color=FF0000]单位为厘米。[/color]
Out函数：  用于处理借出电线，其中参数length表示了还回的长度，[color=FF0000]单位为厘米。[/color]如果成功借出，返回1，否则返回0。

补充：因为有可能有人上一次实验时有剩余的电线，在这一次实验是还回。所以如果出现柜子中的电线总长度大于初始值，或者还回了一段“没被借出”的电线，也是合理的。

测试时的程序可能像下面这样：（伪代码）
int main()
{
    Start();
    if( Out(24) != 参考答案 )
        报错;
    In(10);
    if( Out(128) != 参考答案 )
        报错;
    In(62);
    if( Out(34) != 参考答案 )
        报错;
    if( Out(10000) != 参考答案 )
        报错;
    End();
}

有任何意见或问题请到以下位置提出。
http://www.programfan.com/club/showbbs.asp?id=179737

本帖地址： http://bbs.pfan.cn/post/180278.html

回复列表（共9个回复）

沙发

iAkiak [专家分：8460] 发布于 2006-07-07 13:23:00

#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
struct _iAkiak_33_1
{
    int count[101];// 100以内的应该比较多
    vector<int> len; // 超过100的部分特殊处理
    bool bSorted;

    void Start()
    {
        memset(count, 0, sizeof(count));
        len.clear();
        bSorted = true;

        In(100); // 一开始有一条100厘米的
    }
    void In(int length)
    {
        assert(length > 0);
        if (length <= 100)
            count[length]++;
        else
        {
            if (bSorted && !len.empty() && len.back() > length) // 此时会打乱原有顺序，但暂时不排序
                bSorted = false;
            len.push_back(length);
        }
    }
    int Out(int length)
    {
        assert(length > 0);
        for (int i = length; i <= 100; i++) // 如果需要的长度在100以内，那么找最合适的给他
        {
            if (count[i] > 0)
            {
                count[i]--;
                if (i > length) // 最合适的长度比需要的长，需要剪开
                    In(i - length); // 余下部分放回去
                return 1;
            }
        }
        if (!bSorted) // 需要取超过100的情况，假如len是乱序则需要先排序
        {
            sort(len.begin(), len.end());
            bSorted = true;
        }
        vector<int>::iterator le = lower_bound(len.begin(), len.end(), length); // 二分查找最合适的线
        if (le == len.end()) // 找不到，返回0
            return 0;
        assert(*le >= length);
        int rest = *le - length;
        len.erase(le); // 删除这条
        if (rest > 0) // 需要剪开，还剩下rest长度的线，放回去
            In(rest);
        return 1;
    }
    void End()
    {
        len.clear();
    }
}iAkiak_33_1;

inline void Start(void)
{
    iAkiak_33_1.Start();
}
inline void In(int length)
{
    iAkiak_33_1.In(length);
}
inline int Out(int length)
{
    return iAkiak_33_1.Out(length);
}
inline void End(void)
{
    iAkiak_33_1.End();
}

板凳

songwei [专家分：0] 发布于 2006-07-07 19:20:00

//我大意题意不是很清楚，编程能力不行,初次参加比赛，多多指教!
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
struct node              //单链表存储电线的数据
{
    int length;         //电线的长度
    struct node *next;  //指向下一个结碘
};

typedef struct node  NODE;

NODE *h;

void Start(void)
{
    h=(NODE *)malloc(sizeof(NODE));
    h->length=100;     //初始化为1根电线长度为100厘米
    h->next=NULL;
}
/*void print()//可以在主函数中调用此函数，查看柜子中所有的电线
{
    NODE *p=h;
    while(p!=NULL)
    {
        cout<<p->length<<"  "<<endl;
        p=p->next;
    }
}*/
void In(int length)//处理还回电线,参数length表示了还回的长度
{
    NODE *p=h;
    while(p->next!=NULL)//电线插入到单链表的末尾
        p=p->next;
    NODE *newnode;
    newnode=(NODE *)malloc(sizeof(NODE));
    newnode->next=NULL;
    newnode->length=length;
    p->next=newnode;
}
int  Out(int length)
{
    NODE *p=h;
    int temp_length=100;//临时变量存储找到的电线长度
    NODE *postion=NULL;//找到的合适的电线的位置
    int flag=0;//记录是否找到合适的电线
    while(p!=NULL)
    {
        if(p->length>=length&&p->length<=temp_length)
        {
            temp_length=p->length;
            postion=p;
            flag=1;
            p=p->next;
        }
        else
        {
            p=p->next;
        }
    }
    if(flag)//如果找到合适的电线
    {
        postion->length=postion->length-length;
        //原电线的长度为剩下的部分
    }
    In(length);
  //假设每个人借出去的电线都还回
    return flag;
}
void End(void)
{
    h->next=NULL;//释放申请的单链表
    free(h);
}
//测试代码
int main()
{
    Start();
    if(Out(24)!=1)
        cout<<"不能借出!"<<endl;
    else
        cout<<"成功借出!"<<endl;
    In(10);
    if(Out(128)!=1)
        cout<<"不能借出!"<<endl;
    else
        cout<<"成功借出!"<<endl;
    In(62);
    if(Out(34)!=1)
        cout<<"不能借出!"<<endl;
    else
        cout<<"成功借出!"<<endl;
    if(Out(10000)!=1)
        cout<<"不能借出!"<<endl;
    else
        cout<<"成功借出!"<<endl;
//    print();
    End();
    getch();
    return 0;
}

3 楼

天国龙 [专家分：490] 发布于 2006-07-07 19:35:00

struct elth
{
    int length;
    elth *next,*prev;
};

int s(0);
elth *first,*lest;

void Start(void)
{
    elth *p;
    p=new elth;
    p->length=100;
    p->next=p;
    p->prev=p;
    first=lest=p;
    s++;
}
void In(int length)
{
    elth *p,*q,*t;
    p=new elth;
    p->length=length;
    if (s)
    {
        q=first;
        while (q!=lest && q->length<length)
            q=q->next;
        if (q->length<length)
        {
            p->next=p;
            lest=p;
            q->next=p;
            p->prev=q;
        }
        else
        {
            if (q==first)
            {
                q->prev=p;
                p->next=q;
                first=p;
                p->prev=p;
            }
            else
            {
                t=q;
                q=q->prev;
                q->next=p;
                p->prev=q;
                q=t->next;
                q->prev=p;
                p->next=q;
                /*q->prev->next=p;
                p->prev=q->prev;
                p->next=q;
                q->prev=p;*/
            }
        }
    }
    else
    {
        p->next=p;
        p->prev=p;
        first=lest=p;
    }
    s++;
}

int Out(int length)
{
    elth *p;
    if(s)
    {
        p=first;
        while (p!=lest && p->length<length)
            p=p->next;
        if (p->length<length)
            return 0;
        else
        {
            length=p->length-length;
            if (p==lest)
                lest=p->prev;
            else if (p==first)
                first=p->next;
            else
            {
                p->prev->next=p->next;
                p->next->prev=p->prev;
            }
            delete p;
            s--;
            if (length)
                In(length);
            return 1;
        }
    }
    else return 0;
}
void End(void)
{
    elth *p;
    if (s)
    {
        p=first;
        while (first!=lest)
        {
            first=first->next;
            delete p;
            p=first;
        }
        delete p;
    }
}

4 楼

johnywoo [专家分：1290] 发布于 2006-07-08 23:07:00

//Compiler: VC6.0
//Language: C++
//Date: 2006-7-8

void Start(void);          /* 保证只在实验开始时调用一次 */
void In(int length);       /* 实验开始后、实验结束前可能调用多次 */
int  Out(int length);      /* 实验开始后、实验结束前可能调用多次 */
void End(void);            /* 保证只在实验结束时调用一次 */

//***************************************************************************

//define the struct of Wire
typedef struct _wire {
    int wireLen;
    struct _wire * next;
} Wire;

//make a list wires-->wireMan(wires Manager)
Wire * wireMan=NULL;

void Start()
{
    //initialize
    wireMan=new Wire;
    wireMan->wireLen=100;
    wireMan->next=NULL;
}

void In(int length)
{
    //deal with invalid input
    if (length<=0)
        return;

//    cout << "trying to take back a wire with length of " << length << endl;

    //create a wire
    Wire* w=new Wire;
    w->wireLen=length;
    w->next=NULL;

    //add the new wire to the wireMan
    //wireMan is ordered by the length
    //length of wire in wireMan : short ----> long
    Wire* iWire;
    Wire* jWire;
    if (wireMan!=NULL && wireMan->wireLen>=length)
    {
        w->next=wireMan;
        wireMan=w;
    }
    else if (wireMan!=NULL)
    {
        iWire=wireMan->next;
        jWire=wireMan;
        while (iWire!=NULL)
        {
            if (iWire->wireLen >= length)
            {
                w->next=iWire;
                jWire->next=w;
                break;
            }
            jWire=iWire;
            iWire=iWire->next;
        }
    }
    else
    {
        wireMan=w;
    }

    //if not added,add at the tail
    if (iWire==NULL)
    {
        jWire->next=w;
    }
}

int Out(int length)
{
    //deal with invalid input
    if (length<=0)
        return 0;

//    cout << "trying to take out a wire with length of " << length << endl;

    Wire* iWire;
    Wire* jWire;
    if (wireMan!=NULL && wireMan->wireLen>=length)
    {
        int wireManLen=wireMan->wireLen;
        //take out a wire
        wireMan=wireMan->next;

        //take back the rest wire
        In(wireManLen-length);

        return 1;
    }
    else if (wireMan!=NULL)
    {
        iWire=wireMan->next;
        jWire=wireMan;
        while (iWire!=NULL)
        {
            if (iWire->wireLen >= length)
            {
                //take out a wire
                jWire->next=iWire->next;

                //take back the rest wire
                In(iWire->wireLen-length);

                //withdraw memory
                iWire->next=NULL;
                delete iWire;

                return 1;
            }
            jWire=iWire;
            iWire=iWire->next;
        }
    }

    //no suitable wires or no wire
    return 0;
}

void End()
{
    //withdraw memory
    while (wireMan != NULL)
    {
        Wire* iWire=wireMan;
        wireMan=wireMan->next;
        iWire->next=NULL;
        delete iWire;
    }
}

//*******************************************************************************

5 楼

yxs0001 [专家分：9560] 发布于 2006-07-09 09:19:00

#include <iostream>

using namespace std;

void Start(void);          /* 保证只在实验开始时调用一次 */
void In(int length);       /* 实验开始后、实验结束前可能调用多次 */
int  Out(int length);      /* 实验开始后、实验结束前可能调用多次 */
void End(void);            /* 保证只在实验结束时调用一次 */

struct LNode{
    int length;
    LNode *next;
    LNode(){};
    LNode(int nlength){length = nlength;};
};

//结点在链表中升序排列
LNode *head,*end;
int max;
LNode* Find(int length);//查找小于length的结点中最大者
void Insert(LNode *lnode);//插入
void Append(LNode *lnode);//添加结点
void Delete(LNode *lnode,LNode *prior);//删除结点
void Move(LNode *lnode,int length);//移动结点

LNode* Find(int length)
{
    LNode *p = head;
    LNode *temp;
    while(temp = p->next){
        if(temp->length >= length)
            return p;
        p = temp;
    }
    return p;
}

void Insert(LNode *lnode)
{
    LNode *prior = Find(lnode->length);
    lnode->next = prior->next;
    prior->next = lnode;
}

void Append(LNode *lnode)
{
    end->next = lnode;
    end = lnode;
    end->next = NULL;
}

void Delete(LNode *lnode,LNode *prior)
{
    if (lnode == end)
        end = prior;
    prior->next = lnode->next;
    delete lnode;
}

void Move(LNode *lnode,int length)
{
    lnode->length = length;
    LNode *prior = Find(length);
    lnode->next = prior->next;
    prior->next = lnode;
}

void Start(void)
{
    LNode *all = new LNode(max = 100);
    head = end = new LNode(0);
    head->next = all;
    all->next = NULL;
}

void In(int length)
{
    LNode *in = new LNode(length);
    if(length>max){
        max = length;
        Append(in);
    }
    else
        Insert(in);
}

int  Out(int length)
{
    LNode *prior = Find(length);
    LNode *lnode = prior->next;
    if(lnode){
        if(!(lnode->next))
            max = prior->length;
        if(lnode->length > length){
            if(lnode->length - length > max){
                max = lnode->length - length;
                lnode->length -= length;
            }
            else{
                if (lnode == end)
                    end = prior;
                prior->next = lnode->next;
                Move(lnode,lnode->length - length);
            }
        }
        else
            Delete(lnode,prior);
        return 1;
    }
    else
        return 0;
}

void End(void)
{
    LNode *p = head,*temp;
    while(p->next){
        temp = p->next;
        delete p;
        p = temp;
    }
}

int main()
{
    int r;
    Start();
    r = Out(24);
    In(10);
    r = Out(128);
    In(62);
    r = Out(34);
    r = Out(76);
    End();
    return 0;
}

6 楼

hanshuyujifen [专家分：800] 发布于 2006-07-09 10:53:00

//第一次参加编程比赛，希望多指点
//使用链表存放相关数据
//Dev4.9.9.2下通过
//hanshuyujifen 060709
#include <cstdlib>
#include <iostream>

using namespace std;

typedef struct Lnode
{
        int len;
        Lnode *next;
}Lnode;
Lnode *head;   //链表头
void Start()
{//建立一个空链表，用于存储电线的特征
     head=new Lnode;
     head->len=100;
     head->next=NULL;
}
void End()
{//释放链表

}
void In(int length)
{//还回的电线建立新节点存放
     Lnode *p=new Lnode;
     p->len=length;
     p->next=head->next;
     head->next=p;
}

int Out(int length)
{
//借出电线时，先查找与需要长度最接近的电线。
//然后分割、借出。并将剩余的电线长度存放于原位置
    Lnode *p=head;
    int temp=head->len-length;
    Lnode *k=head;//指针k用来标记查找到元素的位置
    while(p->next!=NULL)
    {
        if(temp<(p->len-length))
        {temp=(p->len-length);k=p;}
        p=p->next;
    }
    if(temp<0)  //temp小于0说明没有找到需要的长度
        return 0;
    else
    {
        k->len=temp;
        return 1;
    }
}

int main(int argc, char *argv[])
{
    Start();
    int i=Out(24);
    cout<<i<<endl;
    In(10);
    cout<<Out(128)<<endl;
    In(62);
    cout<<Out(34)<<endl;
    cout<<Out(10000)<<endl;
    End();
    system("PAUSE");
    return EXIT_SUCCESS;
}

7 楼

szh [专家分：380] 发布于 2006-07-09 11:19:00

//编译器　Dev-C++ 4.9.92
#include <stdio.h>
#include <stdlib.h>
#define L sizeof(Line)

typedef struct line
{
    int length;
    struct line *next;
}Line;

Line *line,*head;

void Insert(Line *tmp)
{
    Line *p=head, *prev=head;
    while(p->next!=NULL && tmp->length>p->length)
    {
         prev=p;
         p=p->next;
    }
    if(tmp->length<=p->length)
    {
         prev->next=tmp;
         tmp->next=p;
    }
    else
    {
        p->next=tmp;
        tmp->next=NULL;
    }
}

void Start(void)
{
     if(!(head=(Line*)malloc(L)))   exit(1);
     if(!(line=(Line*)malloc(L)))   exit(1);
     line->next=NULL;
     line->length=100;
     head->next=line;
     head->length=0;
}

void In(int length)
{
    Line *tmp;
    if(!(tmp=(Line*)malloc(L)))     exit(1);
    tmp->length=length;
    Insert(tmp);
}

int Out(int length)
{
    Line *p=head, *prev=head;
    int out=1;
    while(p->next!=NULL && p->length<length)
    {
         prev=p;
         p=p->next;
    }
    if(p->length>length)
    {
         Line *tmp=p;
         tmp->length-=length;
         prev->next=p->next;
         Insert(tmp);
    }
    else if(p->length==length)
    {
         Line *tmp=p;
         prev->next=p->next;
         free(tmp);
    }
    else
    {
        out=0;
    }
    return out;
}

void End(void)
{
     Line *p=head;
     while(p)
     {
         Line *current=p;
         p=p->next;
         free(current);
     }
}

8 楼

magicalking [专家分：150] 发布于 2006-07-09 11:38:00

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <ctype.h>

using namespace std;

class rope{
      public:
             void start();
             void in(int);
             int out(int);
             void end();
      private:
              vector<int>_rope;
              };

void rope::start(){
     _rope.push_back(100);
     }

void rope::in(int length){
     _rope.push_back(length);
     sort(_rope.begin(),_rope.end());
     }

int rope::out(int length){
    vector<int>::iterator it;
    if((it=lower_bound(_rope.begin(),_rope.end(),length))==_rope.end())
    return 0;
    else {
         *it-=length;
         sort(_rope.begin(),_rope.end());
         return 1;
         }
}

void rope::end(){}

rope r1;

main(){

    r1.start();
    char c;
    bool q=1;

    do{

    cout<<"\n(b)orrow or (r)eturn or (q)uit?\n";
    cin>>c;
    tolower(c);

    switch(c){
              case 'b':
    cout<<"how long do you want?\n";
    int length;
    cin>>length;
    if(!r1.out(length))
    cout<<"no matched rope exist!\n";
    else
    cout<<"ok,remember to return in time!\n";
    break;

              case 'r':
    cout<<"how long do you want to return?\n";
    int length2;
    cin>>length2;
    r1.in(length2);
    cout<<"ok thank you!\n";
    break;

              case 'q':
    q=0;
    break;
              default:
    cout<<"input error!reinput!\n";
}//switch end
}//do end
while(q);
r1.end();
}

9 楼

eastcowboy [专家分：25370] 发布于 2006-07-09 13:10:00

时间到……

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第34次编程比赛题目（第1题）

回复列表（共9个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第34次编程比赛题目（第1题）

回复列表 （共9个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共9个回复）