蚂蚁问题，有人能帮忙编一下嘛 - C语言论坛

已结贴√ 问题点数：5 回复次数：10

蚂蚁问题，有人能帮忙编一下嘛

蚂蚁

一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米/秒。当两只蚂蚁相撞时，二者同时掉头（掉头时间忽略不计）。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。

输入格式：
输入的第一行为数据组数。每组数据的第一行为3个正整数L、T、n（0<=n<=10000）；以下n行每行描述一只蚂蚁的初始位置，其中，整数x为蚂蚁距离木棍左端的距离（单位：厘米），字母表示初始朝向（L表示朝左，R表示朝右）。
输出格式：
对于每组数据，输出n行，按输入顺序输出每只蚂蚁的位置和朝向（Turing表示正在碰撞）。在第T秒之前已经掉下木棍的蚂蚁（正好爬到木棍边缘的不算）输出Fell off。

样例输入：
2
10 1 4
1 R
5 R
3 L
10 R
10 2 3
4 R
5 L
8 R
样例输出：
Case #1:
2 Turing
6 R
2 Turing
Fell off

Case #2:
3 L
6 R
10 R

搜索更多相关主题的帖子: 字母　蚂蚁　正整数　

第 2 楼

得分:0

程序代码：

写了输入函数，但是关于碰撞回头那块的函数不会写
#include "stdio.h"

void main(int argc,char*argv[])
{
    int k,L,T,n;
    scanf("%d",&k);
    for(int ki=1;ki<=k;ki++)
    {
        scanf("%d%d%d",&L,&T,&n);//连续输出三个数三个百分浩连在一起
        for(int i=0;i<n;i++)
        {
          int p;char c;
          scanf("%d %c",&p,&c);//输入两个数之间有空格就这样真的有空格
        }
        
     }

}

第 3 楼

得分:0

我可以告诉你下我的思想！

仗剑走天涯，网络论英雄。

第 4 楼

得分:0

#include <stdio.h>
#include <stdlib.h>
#include EER 0xffffffff
typedef struct
{
    int Distance;
    char Dir;
}AntData;
void Ant_go_next(AntData k[],int n,int length); /// one step
int main()
{
    int TestCase,i;
    int Length,AcoSec,NumAnt;
    int calc,Time;
    AntData TestOne[100];
    scanf("%s",&TestCase);
    while(TestCase--)
    {
        scanf("%d%d%d",&Length,&AcoSec,&NumAnt);
        i = 0;
        cal =NumAnt;
        Time = AcoSec;
        while(cal--)
        {
            scanf("%d%c",&TestOne[i].Distance,&TestOne[i].Dir);
            i++;
        }
        /// sort by Distance
        {
            ;
        }
        for(int j = 0;j < Time;j++) /// one second one step
        {
            Ant_go_next(TestOne,NumAnt,Length);
        }
        /// prompt print
        {
        ;
        }
    }
return 0;
}

void Ant_go_next(AntData k[],int n,int length) /// one step
{
   for(int i = 0;i < n; i++)
    {
        if((i!=n-1)&&(k[i].Dir!=k[i+1].Dir)&&(k[i].Distance==k[i+1].Distance)) /// right
        {
            if(k[i].Dir=='R')
            {
                 k[i].Dir = 'L';
                 k[i].Distance--;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }

            if(k[i].Dir=='L')
            {
                k[i].Dir = 'R';
                 k[i].Distance++;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }

        }

        else if((i!=1)&&(k[i].Dir!=k[i-1].Dir)&&(k[i].Distance==k[i-1].Distance)) /// left
        {
            if(k[i].Dir=='R')
            {
                 k[i].Dir = 'L';
                 k[i].Distance--;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }

            if(k[i].Dir=='L')
            {
                k[i].Dir = 'R';
                 k[i].Distance++;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }

        else
        {
            if(k[i].Dir=='R')
            {
                 k[i].Distance++;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }

            if(k[i].Dir=='L')
            {
                 k[i].Distance--;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }
        }

    }
}

觉得另一该留给你完成啦！！！！不合理的地方还请指点！

仗剑走天涯，网络论英雄。

第 5 楼

得分:0

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include EER 0xffffffff
typedef struct
{
    int Distance;
    char Dir;
}AntData;
void Ant_go_next(AntData k[],int n,int length); /// one step
int main()
{
    int TestCase,i;
    int Length,AcoSec,NumAnt;
    int calc,Time;
    AntData TestOne[100];
    scanf("%s",&TestCase);
    while(TestCase--)
    {
        scanf("%d%d%d",&Length,&AcoSec,&NumAnt);
        i = 0;
        cal =NumAnt;
        Time = AcoSec;
        while(cal--)
        {
            scanf("%d%c",&TestOne[i].Distance,&TestOne[i].Dir);
            i++;
        }
        /// sort by Distance
        {
            ;
        }
        for(int j = 0;j < Time;j++) /// one second one step
        {
            Ant_go_next(TestOne,NumAnt,Length);
        }
        /// prompt print 
        {
        ;
        }
    }
return 0;
}

void Ant_go_next(AntData k[],int n,int length) /// one step
{
   for(int i = 0;i < n; i++)
    {
        if((i!=n-1)&&(k[i].Dir!=k[i+1].Dir)&&(k[i].Distance==k[i+1].Distance)) /// right 
        {
            if(k[i].Dir=='R')
            {
                 k[i].Dir = 'L';
                 k[i].Distance--;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }
               
            if(k[i].Dir=='L')
            {
                k[i].Dir = 'R';
                 k[i].Distance++;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }
                
        }
        
        else if((i!=1)&&(k[i].Dir!=k[i-1].Dir)&&(k[i].Distance==k[i-1].Distance)) /// left 
        {
            if(k[i].Dir=='R')
            {
                 k[i].Dir = 'L';
                 k[i].Distance--;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }
               
            if(k[i].Dir=='L')
            {
                k[i].Dir = 'R';
                 k[i].Distance++;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }
        
        else
        {
            if(k[i].Dir=='R')
            {
                 k[i].Distance++;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }
               
            if(k[i].Dir=='L')
            {
                 k[i].Distance--;
                 if(k[i].Distance > length || k[i].Distance < 0)
                    k[i].Distance = EER;
            }
        }
        
    }
}

觉得另一该留给你完成啦！！！！不合理的地方还请指点！

仗剑走天涯，网络论英雄。

第 6 楼

得分:0

回复 5 楼嗜血老妖

void Ant_go_next(AntData k[],int n,int length) 表示没看懂

第 7 楼

得分:2

由于前面的蚂蚁已经从左到右拍好续了该函数只需要判断与i只相邻的情况从而给定i只在下一步的位置和方向

仗剑走天涯，网络论英雄。

第 8 楼

得分:3

这是一道算法题，若你一秒一秒的去推演就落了下乘。
考虑 A B C 三只蚂蚁
不管经过多少秒，不管碰撞多少次，B永远在A的右边，永远在C的左边；
B若往左走N步，不管碰撞过多少次，都将导致B左边N步处出现一只蚂蚁，尽管这只蚂蚁可能是B自身，也可能不是B自身
B若往右走N步，不管碰撞过多少次，都将导致B右边N步处出现一只蚂蚁，尽管这只蚂蚁可能是B自身，也可能不是B自身

以下代码是我随手写的，可能有错，仅供参考

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct foo
{
    int inputorder;
    int position;
    char direction;
};
int compare1( const void* a, const void* b )
{
    return (*(const struct foo*)a).position - (*(const struct foo*)b).position;
}
int compare2( const void* a, const void* b )
{
    return (*(const struct foo*)a).inputorder - (*(const struct foo*)b).inputorder;
}

void bar( int L, int T, int N, struct foo s[] )
{
    qsort( s, N, sizeof(s[0]), &compare1 );

    struct foo s2[10000];
    memcpy( s2, s, N*sizeof(s[0]) );
    for( int i=0; i!=N; ++i )
        s[i].position = s[i].direction=='L' ? s[i].position-T : s[i].position+T;
    qsort( s, N, sizeof(s[0]), &compare1 );

    for( int i=0; i!=N; ++i )
    {
        s[i].inputorder = s2[i].inputorder;

        if( s[i].position<0 || s[i].position>L )
            s[i].direction = 'F';
        else if( i!=N && s[i].position==s[i+1].position )
            s[i].direction='T', s[i+1].direction='T';
    }

    qsort( s, N, sizeof(s[0]), &compare2 );
}

int main()
{
    int cnt;
    scanf( "%d", &cnt );
    for( int idx=0; idx!=cnt; ++idx )
    {
        int L, T, N;
        scanf( "%d%d%d", &L, &T, &N );

        struct foo s[10000];
        for( int i=0; i!=N; ++i )
        {
            s[i].inputorder = i;
            scanf( "%d %c", &s[i].position, &s[i].direction );
        }

        bar( L, T, N, s );

        printf( "Case #%d:\n", idx+1 );
        for( int i=0; i!=N; ++i )
        {
            switch( s[i].direction )
            {
            case 'F':
                printf( "Fell off\n" );
                break;
            case 'T':
                printf( "%d Turing\n", s[i].position );
                break;
            default:
                printf( "%d %c\n", s[i].position, s[i].direction );
                break;
            }
        }
        printf( "\n" );
    }

    return 0;
}

第 9 楼

得分:0

抽烟归来，为了便于理解，我举个例子吧
假设一开始从左到右分别是 4R 5L 8R ----------- 序列1
若不考虑碰撞，2秒后分别变为 6R 3L 10R ------- 序列2
将 6R 3L 10R 从左到右排序，变为 3L 6R 10R --- 序列3
将序列1和序列2一一对应，可知 4R变成了3L、5L变成了6R、8R变成了10R
整个算法的核心就是一个简单的排序

第 10 楼

得分:0

回复 9 楼 rjsp

厉害