第三十一次编程比赛第二题题目

主题：第三十一次编程比赛第二题题目

boxertony [专家分：23030] 发布于 2006-06-15 20:33:00

整数变换问题。关于整数i的变换f和变换g的定义如下：f(i)=3i; g(i)=└i/2┘。试设计一个算法，对于给定的两个整数n和m，用最少的f和g变换次数将n变换为m。例如，可以将整数15用4次变换为整数4，即4=gfgg(15)。
    具体变换如下：g(15)=7  g(7)=3  f(3)=9  g(9)=4

// f函数
inline int f(int i)
{
    return 3*i;
}

// g函数
inline int g(int i)
{
    return (i>>1);
}

// 函数接口
// [in]n   -- 待转换正整数 (0<n<=1000)
// [in]m   -- 目标正整数   (0<m<=1000)
// [out]fs -- 存放转换步骤，比如 15=>4 为 "gfgg" （请一定加上字符串结束标志符'\0'）
// [return]-- 转换的最少步数（当无解时，返回INT_MAX）
int transform(int n, int m, char *fs);

char *getid(char *id)
{
    return strcpy(id, "boxertony"); // 请用自己的id替换掉"boxertony"
}

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

回复列表（共16个回复）

沙发

overfly [专家分：3230] 发布于 2006-06-15 20:44:00

这个题目好像过于简单啊[em8]

板凳

yunzhou008 [专家分：410] 发布于 2006-06-15 22:21:00

我错了........

3 楼

yunzhou008 [专家分：410] 发布于 2006-06-15 22:24:00

我错了.......

4 楼

iAkiak [专家分：8460] 发布于 2006-06-16 02:03:00

// A*了，不知道是否有数学方法

#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <map>

using namespace std;

#ifdef _MSC_VER
typedef __int64 bigint;
#else
typedef long long bigint;
#endif

struct Node
{
    Node(){}
    Node(bigint _v, const string &_path) :
    v(_v), path(_path)
    {
    }
    int GetMinStep(int m) const
    {
        if (v < m)
            return int(log(double(m) / double(v)) / log(3)) + path.size();
        if (v > m)
            return int(log(double(v) / double(m)) / log(2)) + path.size();
        return path.size();
    }
    bigint v;
    string path;
    struct Cmp
    {
        Cmp(int _m):m(_m){}
        int m;
        bool operator ()(const Node &a, const Node &b) const
        {
            return a.GetMinStep(m) > b.GetMinStep(m);
        }
    };
};

int transform(int n, int m, char *fs)
{
    Node t;
    vector<Node> q;
    q.push_back(Node(n, ""));
    map<bigint, bool> visit;
    visit[n] = true;
    while(!q.empty())
    {
        t = q.front();
        if (t.v == m)
            break;
        pop_heap(q.begin(), q.end(), Node::Cmp(m));
        q.pop_back();
        if (t.v > 1)
        {
            bigint x = t.v/2;
            map<bigint, bool>::iterator it = visit.find(x);
            if (it == visit.end())
            {
                visit.insert(it, pair<bigint, bool>(x, true));
                q.push_back(Node(x, 'g' + t.path));
                push_heap(q.begin(), q.end(), Node::Cmp(m));
            }
        }
        bigint x = t.v * 3;
        map<bigint, bool>::iterator it = visit.find(x);
        if (it == visit.end())
        {
            visit.insert(it, pair<bigint, bool>(x, true));
            q.push_back(Node(x, 'f' + t.path));
            push_heap(q.begin(), q.end(), Node::Cmp(m));
        }
    }
    if (q.empty())
        return INT_MAX;
    strcpy(fs, t.path.c_str());
    return t.path.size();
}

char *getid(char *id)
{
    return strcpy(id, "iAkiak"); // 请用自己的id替换掉"boxertony"
}

5 楼

fenix124 [专家分：70] 发布于 2006-06-16 10:02:00

//我的算法根本就不高效,只是大致把答案凑出来而已.
//开始凑的时候把visit[]开到了10000000然后慢慢缩小,最后发现20000就可以,15000
//就不行了.主要的思想是宽搜,答案未必正确.
//测试时把所有的全局变量和函数拷过去.

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

int map[1001][20000];
int visit[20000];
struct node
{
    int x;
    int step;
}q[20000];

int f,r;

void calc(int m)
{
    int t,x,y;
    t = 1;
    f = r = 0;
    q[0].x = m;
    q[0].step = 0;
    visit[m] = 1;
    while(f <= r && t < 1000)
    {
        x = q[f].x;
        y = x/2;
        if(y && !visit[y])
        {
            visit[y] = 1;
            q[++r].x = y;
            q[r].step = q[f].step+1;
            if(y <= 1000) t++;
            map[m][y] = q[f].step+1;
        }
        y = x*3;
        if(y < 20000 && !visit[y])
        {
            visit[y] = 1;
            q[++r].x = y;
            q[r].step = q[f].step+1;
            if(y <= 1000) t++;
            map[m][y] = q[f].step+1;
        }
        f++;
    }
    memset(visit,0,20000*4);
}

int solve(int m,int n)
{
    if(m == n) return 0;
    if(map[m][n]) return map[m][n];
    calc(m);
    return map[m][n];
}

int transform(int n, int m, char *fs)
{
    int x,y,p,z,i;
    x = n;
    y = m;
    p = 0;
    z = solve(n,m);
    for(i = 0;i < z;i++)
    {
        if( y%3 == 0 && map[x][y] == map[x][y/3]+1)
        {
            fs[i] = 'f';
            y /= 3;
        }
        else if(map[x][y] == map[x][y*2+1]+1 )
        {
            fs[i] = 'g';
            y = y*2+1;
        }
        else if(map[x][y] == map[x][y*2]+1 )
        {
            fs[i] = 'g';
            y = y*2;
        }
    }
    fs[z] = 0;
    return z;
}

char *getid(char *id)
{
    return strcpy(id, "fenix124");
}

int main()
{
    int i,j,n;
    char ch[100];
    while(scanf("%d %d",&i,&j) != EOF)
    {
        n = transform(i,j,ch);
        printf("%d %s\n",n,ch);
        memset(ch,0,100);
    }
    return 0;
}

6 楼

天边蓝 [专家分：1810] 发布于 2006-06-16 13:21:00

/*
删除
*/

7 楼

fantasyzzz [专家分：0] 发布于 2006-06-16 14:53:00

inline int f(int i)
{
    return 3*i;
}
inline int g(int i)
{
    return (i>>1);
}
char* getid(char *id)
{
    return strcpy(id, "fantasyzzz");
}
int transform(int n, int m, char *fs)
{
    if(n==m)
        return 0;
    if(n*m<0)
        return INT_MAX;

    int length=0;
    int number[100];
    int index=0;

    do
    {
        if(n<m)
        {
            n=f(n);
            fs[index]='f';
        }
        else
        {
            n=g(n);
            fs[index]='g';
        }
        ++length;
        for(int i=0;i<index;++i)
            if(number[i]==n)
                return INT_MAX;
        number[index++]=n;
        if(n==m)
            break;
    }while(true);

    return length;
}

8 楼

kcalf [专家分：0] 发布于 2006-06-16 21:36:00

#include <iostream>
using namespace std;
char *getid(char *id);
int transform(int n, int m, char *fs);
inline int f(int i);
inline int g(int i);
void main()
{
    char c[10];
    int n,m;
    *c='\0';
    cout<<"输入n和m(空格分隔):";
    cin>>n>>m;
    cout<<"结果:";
    if(transform(n,m,c)!=INT_MAX)
        cout<<"\n函数使用情况:"<<c<<endl;
    else
    cout<<"无解!\n";
    cout<<"\n参赛者:"<<getid(c)<<endl;
}

int transform(int n, int m, char *fs)
{
    static k=0;
    if(n>1000||m>1000||m<=0||n<=0)  //m,n值的条件
        return INT_MAX;
    if(k>10)return INT_MAX;
    //没有搞懂什么时候是无解的
    if(n>m){
        k++;
        if(transform(g(n),m,fs)==INT_MAX)return INT_MAX;
        //递归调用,为了逆向输出序列
        strcat(fs,"g\0");
    }
    if(n<m){
        k++;
        if(transform(f(n),m,fs)==INT_MAX)return INT_MAX;
        //递归调用,为了逆向输出序列
        strcat(fs,"f\0");
    }
    return 1;
}

char *getid(char *id)
{
    return strcpy(id, "KelSat");
}

inline int f(int i)
{
    return 3*i;
}

inline int g(int i)
{
    return (i>>1);
}

//第一次来比赛,不足之处,还请鉴谅![em1]

9 楼

太没劲了 [专家分：2050] 发布于 2006-06-17 10:50:00

VC6 下测试通过

#include<limits.h>
#include<iostream.h>
#include<vector>
#include<map>

using namespace std;

struct _ACT
{
    char  op;
    short parent;
};

static vector<short> Srclist;
static map<short,_ACT *>  Searchmap;
static short Dst,Getflag,Lnuml[256],Lnum_cur;

void solve(short src)
{

#define _ADDITEM(CURV,CURADD,OP,SRC)    do { Srclist.push_back(CURV); \
CURADD= new _ACT(), CURADD->op=OP, CURADD->parent=(SRC); \
Searchmap[CURV] = (CURADD); \
if( (CURV)==Dst ) \
{ \
    Getflag = 1; \
    return; \
} }while(0)

    short curv,i;
    _ACT *curadd;

    for(i=0;i<2; ++i)
    {
        if( (curv=src*2+i)>src && Searchmap.find(curv)==Searchmap.end() )
            _ADDITEM(curv,curadd,'g',src);
    }
    if( src && (curv=src/3) && !(src%3) && Searchmap.find(curv)==Searchmap.end() )
        _ADDITEM(curv,curadd,'f',src);
}

int transform(int n, int m, char *fs)
{
    _ACT curitem,*curp;
    int num=INT_MAX;

    Dst = n, Getflag = 0, Lnum_cur=0;
    Srclist.push_back(m);
    curitem.op = 0, curitem.parent = 0;
    Searchmap[0] = &curitem;
    Lnuml[Lnum_cur++] = 0, Lnuml[Lnum_cur++]=1;
    do
    {
        for(short i=Lnuml[Lnum_cur-2] ; i<Lnuml[Lnum_cur-1] && !Getflag; ++i)
            solve(Srclist[i]);
        if( Getflag )
        {
            short j=Srclist[Srclist.size()-1],k;

            for(k=0; j>0 && (k+2)<=Lnum_cur && (curp=Searchmap[j]); ++k)
                fs[Lnum_cur-k-2] = curp->op, j = curp->parent;

            fs[k] = 0, num = k;
        }
        else Lnuml[Lnum_cur++] = Srclist.size();
    } while(!Getflag && Lnum_cur<250);
    map<short,_ACT *>::iterator iter=Searchmap.begin();
    for(;iter!=Searchmap.end(); iter++)
        if( (*iter).first ) delete (_ACT *)((*iter).second);
    Srclist.clear();
    Searchmap.clear();

    return(num);
}

char *getid(char *id)
{
    return strcpy(id, "太没劲了"); // 请用自己的id替换掉"boxertony"
}

10 楼

weege [专家分：30] 发布于 2006-06-17 14:37:00

real

我来回复

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

主题：第三十一次编程比赛第二题题目

回复列表（共16个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第三十一次编程比赛第二题题目

回复列表 （共16个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共16个回复）