| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 802 人关注过本帖
标题:帮忙求解一条题目!跪谢啊!
只看楼主 加入收藏
jasonfungsing
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-3-29
收藏
 问题点数:0 回复次数:7 
帮忙求解一条题目!跪谢啊!
a multiplication (4 marks). Consider a multiplication of the form
                  * * *
               x * * *
                 -------
               * * * *
            * * * *
         * * * *
      ----------------
         * * * * * *
Each star stands for a digit, with the leftmost star on each line with stars standing for a nonzero
digit. This multiplication has 3 partial products (the three lines between the two horizontal bars).
Give all solutions such that:
 all partial products are made up of the same digits (a given digit occurs in every partial
product or in none of them);
 the rst and second partial products are di erent;
 the orderings of digits in the second and third partial products are inverse of each other (such
as 1424 and 4241);
 the third partial product is the sum of the rst two partial products.
The output of your program,  should be lines of the form
... x ... = ......, with ...., .... and .... as partial products, is a solution.
搜索更多相关主题的帖子: 求解 
2008-03-29 20:22
now
Rank: 1
来 自:广州
等 级:新手上路
帖 子:544
专家分:0
注 册:2007-11-9
收藏
得分:0 
又是一道作业

GIS
Geographic Information System
你在哪里?——》你的坐标?
2008-03-29 20:28
jxt598598
Rank: 1
等 级:新手上路
帖 子:149
专家分:0
注 册:2007-6-13
收藏
得分:0 
英文版 太强 了

qq:304742297
2008-03-29 20:37
hoodlum1980
Rank: 2
来 自:浙江大学
等 级:论坛游民
威 望:2
帖 子:289
专家分:23
注 册:2008-2-24
收藏
得分:0 
我先帮你找到一个答案;代码需要修改修改稍后才能附上:
       423
    *  743
 ------------
      1269
     1692
    2961
-------------
=   314289

这个题的英文意思我仔细看了看,好像英文是不是有些拼写错误啊?有三个主要要求:
(1)2961=1269+1692;即第三个中间结果要等于前两个中间结果的和;(the third partial product is the sum of the rst two partial products.)
(2)三个中间结果的数字是同样的四个数字(都是1,2,6,9组成);(all partial products are made up of the same digits (a given digit occurs in every partial product or in none of them));
(3)第二个和第三个中间结果的数位正好顺序相反,例如第二个是1692,第三个是反过来,2961.(the orderings of digits in the second and third partial products are inverse of each other (such as 1424 and 4241));

最终的输出应该是这样的:
[bo]423 x 743 = 314289, with 1269, 1692 and 2961 as partial products, is a solution.[/bo]

[[it] 本帖最后由 hoodlum1980 于 2008-3-29 23:57 编辑 [/it]]
2008-03-29 23:22
hoodlum1980
Rank: 2
来 自:浙江大学
等 级:论坛游民
威 望:2
帖 子:289
专家分:23
注 册:2008-2-24
收藏
得分:0 
此题目的完整代码如下:
程序代码:
/*

 * descrip : 找到一个解,代替题目中的星号(要求略)

 * code by : hoodlum1980

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

/*判断一个数,是否是另一个数的逆序数位,用字符串形式判断*/
int judgeDigits(char *x1,char *x2)
{
    if(strlen(x1)!=4 || strlen(x2)!=4) return 0; /*不是四位数则返回false*/
    if(x1[0]!=x2[3] || x1[1]!=x2[2] || x1[2]!=x2[1] || x1[3]!=x2[0]) return 0;
    return 1;/*符合逆序,返回true!*/
}

/*判断x1和x2字符串是否由相同的字符组成*/
int judgeCharacters(char *x1,char *x2)
{
    int i=0,length=strlen(x1);
    if(length!=strlen(x2)) return 0;
    for(;i<length;i++)
        if(!strchr(x1,x2[i]) || !strchr(x2,x1[i])) return 0;   /*如果有一个字符不在另一个字符串中,返回false*/
    return 1; 
}

/*

 *      xxx  //x;第一个乘数

 *      cba  //cba;第二个乘数由a,b,c组成

 *  -------

 *     &&&&  //t1=a*x;中间结果1;

 *    &&&&   //t2=b*x

 *   &&&&    //t3=c*x

 *  -------

 *   &&&&&&  //result;最终结果

 */

void main()
{
    int a,b,c,t1,t2,t3;/*x是第一个乘数,第二个乘数是“cba”的形式组成,中间结果是t1,t2,t3*/
    unsigned long x,result;
    char str1[6],str2[6],str3[6];
    clrscr();
    for(x=100;x<1000;x++)
    {
        for(a=1;a<10;a++)
        {
            for(b=1;b<10;b++)
            {
                if(b==a) continue;
                c=a+b; /*这里的c使得t3=t1+t2!*/
                if(c>9) continue;
                result=(a+b*10+c*100)*x; /*计算出相乘的结果!*/
                if(result<100000 || result>999999) continue; /*相乘最终结果必须是6位数!*/
                t1=a*x; /*三个中间结果*/
                if(t1<1000 || t1>9999) continue; /*所有中间结果必须是4位数,t2和t3的位数将在judgeDigits中检验*/
                t2=b*x;
                t3=c*x;
                /*把t2和t3打印成字符串*/
                itoa(t1,str1,10);
                itoa(t2,str2,10);
                itoa(t3,str3,10);
                /*检验t2和t3是否正好数位顺序相反*/
                if(!judgeDigits(str2,str3)) continue;
                /*校验t1的字符是否和t2和t3的字符一致!*/
                if(!judgeCharacters(str1,str2)) continue;                
                    
                /*到达这里时已经通过了所有的验证,说明这是一个解,输出它!*/
                printf("%ld x %d%d%d = %ld, with %d, %d and %d as partial products, is a solution.\n",x,c,b,a,result,t1,t2,t3);
                printf("     %ld\n",x);
                printf(" *   %d%d%d\n",c,b,a);
                printf(" -------\n");
                printf("    %d\n",t1);
                printf("   %d\n",t2);
                printf("  %d\n",t3);
                printf(" -------\n");
                printf(" =%ld\n\n",result);
            }
        }
    }
}

最终输出为前一回帖中的解。上面的代码,主循环中的主体检验部分 大约需要进行 900 * 9 * 8 = 64800 次左右。当然,在代码中我争取尽快的把不是解的当前搜索continue掉。

[[it] 本帖最后由 hoodlum1980 于 2008-3-30 13:37 编辑 [/it]]
2008-03-29 23:38
aipb2007
Rank: 8Rank: 8
来 自:CQU
等 级:贵宾
威 望:40
帖 子:2879
专家分:7
注 册:2007-3-18
收藏
得分:0 
典型暴力法

Fight  to win  or  die...
2008-03-30 00:17
hoodlum1980
Rank: 2
来 自:浙江大学
等 级:论坛游民
威 望:2
帖 子:289
专家分:23
注 册:2008-2-24
收藏
得分:0 
刚才的代码中的第一个判断两个数字字符串是否正好数位逆序时,因为根据题意,要判断的两个数字都是4位数,所以判断的逻辑写死在代码里了,这样的缺点是这个函数不够灵活,无法适应题目要求变了或者其他应用场合。干脆把这个函数去掉了,改为更通用的方式,即“strcmp(strrev(x1),x2) = 0”是解的一个必要条件。在judgeCharacters函数主要是判断字符串x1中是否包含x2中的所有字符,为了效率起见,这个函数实际上在逻辑上仅仅检验了两个字符串由同一组字符组成的一个必要条件,即检验的是x2是x1的一个字符子集,例如("4567","7777777777")这样的字符串也是判通过的。即judgeCharacters(x1,x2) && judegeCharacters(x2,x1),才能推断出x1和x2的字符组成相同,但在这里只判断一个必要条件就足够可以把不是解的搜索过滤掉了。实际上完备的写法应该是
int judgeCharacters(char *x1,char *x2)
{
    int i,length=strlen(x1);
    if(length!=strlen(x2)) return 0;
    for(i=0;i<length;i++)
        if(strchr(x1,x2[i])==NULL || strchr(x2,x1[i])==NULL ) return 0;
    return 1;
}
代码如下:
程序代码:
/* code by : hoodlum1980 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*判断字符串x1是否包含x2中的所有字符,例如,("abcd","dbca")=true,("abcd","aba")=true,("abcd","af")=false; */
int judgeCharacters(char *x1,char *x2)
{
    int i=0;
    for(;i<strlen(x2);i++)
        if(strchr(x1,x2[i])==NULL) return 0;  /*如果在字符串x2中有一个字符不在x1中,返回false*/
    return 1;
}
void main()
{
    int a,b,c,t1,t2,t3;/*x是第一个乘数,第二个乘数是“cba”的形式组成,中间结果是t1,t2,t3*/
    unsigned long x,result;
    char str1[6],str2[6],str3[6];
    clrscr();
    for(x=100;x<1000;x++)
    {
        for(a=1;a<10;a++) /*根据题意,显然a,b,c都不为0*/
        {
            for(b=1;b<10;b++)
            {
                if(b==a) continue;
                c=a+b; /*这里的c使得t3=t1+t2!*/
                if(c>9) continue;
                result=(a + b*10 + c*100)*x; /*计算出相乘的结果!*/
                if(result<100000 || result>999999) continue; /*最终结果必须是6位数!*/
                t1=a*x; /*三个中间结果*/
                if(t1<1000 || t1>9999) continue; /*所有中间结果必须是4位数*/
                t2=b*x;
                if(t2<1000 || t2>9999) continue;
                t3=c*x;
                if(t3<1000 || t3>9999) continue;
                /*把t2和t3打印成字符串*/
                itoa(t2,str2,10);
                itoa(t3,str3,10);
                /*检验t2和t3是否正好数位顺序相反*/
                if(strcmp(strrev(str2),str3)!=0) continue;
                /*校验t1的字符是否和t2(t3)的字符一致!*/
                itoa(t1,str1,10);
                if(!judgeCharacters(str1,str3)) continue;
                /*到达这里时已经通过了所有的验证,说明这是一个解,输出它!*/
                printf("%ld x %d%d%d = %ld, with %d, %d and %d as partial products, is a solution.\n",x,c,b,a,result,t1,t2,t3);
            }
        }
    }
}


[[it] 本帖最后由 hoodlum1980 于 2008-3-30 13:31 编辑 [/it]]
2008-03-30 00:27
jasonfungsing
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-3-29
收藏
得分:0 
谢谢谢谢啊,真的非常感谢,这条题目已经让我快死了,感谢救命啊!!
2008-03-30 07:16
快速回复:帮忙求解一条题目!跪谢啊!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020708 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved