华为面试题，改了一下，你会吗？^_^
一个五位数字ABCDE*4=EDCBA，这五个数字不重复，请编程求出来.要求：不准用for,while,if，switch语句
[解决办法]
难道goto有出场的机会了？
[解决办法]
刚想了下,用?:是很简单的绕开if判断的方法, 感觉这个可行
伪码:
void foundNum(int num)
{
int temp = num*4;
string srcNum=int2str(num);
string dstNum=int2str(temp);
strlen(srcNum)> 5? return : (nop); //退出条件
(reverse(dstNum)==(srcNum) && (foundRepeatNum(srcNum)==-1 )?(printf( "found "), return ):foundNum(num+1);
}
递归加 "?: "表达式
reverse()反转字符串
foundRepeatNum()是否有重复字符
可用相应的标准函数或者自己写一个
[解决办法]
我觉得用goto好，
[解决办法]
ABCDE*4=EDCBA
很显然，A不是1，就是2，为0就不是五位数，为> 2则乘积不会是五位数
因为4*E的个位数是A，则A=2
所以题目变成2BCDE*4=EDCB2
显然，E是8（原因，乘以4个位为2的只有3，8，而根据高位2*4> =8，它只能为8
所以变成2BCD8 * 4 = 8DCB2
既然BCD8*4没有进位，因此B只能是0,1,2
假设B=0，则CD8*4=DC02, 4*D的尾数必须为7，这肯定不可能
假设B=1，则1CD8*4 = DC12，4*D的个位数为8，D必然＝7，因为1*4> 2
1C78*4=7C12 C*4 = 30+C-3, C=9，满足
假设B=2，则2CD8 * 4= DC22, D=8或者9，根据C等于4*D+3的个位，可以得出C等于5或者9
所以等式必须为2588 *4 或者2998*4，很显然都不满足
所以只能是(A,b,C,d,e)=(2,1,9,7,8)
[解决办法]
呵呵，使用递归，不过递归函数用模板实现，然后写个特化函数，用来在条件结束时执行。
比如计算1-100的累加值，
template < int size >
int sum()
{
return size + sum <size-1> ();
}
template <>
int sum <1> ()
{
return 1;
}
int result = sum <100> ();
用这种方法，再综合楼上的兄弟们的方法，来解决楼主的问题。
[解决办法]
template <int i>
int result()
{
return ((i> =10000 && i==(10000*(i%10) + 1000*((i/10)%10)) + 100*((i/100)%10))+10*((i/1000)%10)) + ((i/10000)%10)))?(i):(template sum <i-1> ()));
}
#include <iostream>
using namespace std;
int main()
{
cout < < result <99999> < < endl;
}
[解决办法]
少乘了4
template <int i>
int result()
{
return ((i> =10000 && i*4==(10000*(i%10) + 1000*((i/10)%10)) + 100*((i/100)%10))+10*((i/1000)%10)) + ((i/10000)%10)))?(i):(template sum <i-1> ()));
}
#include <iostream>
using namespace std;
int main()
{
cout < < result <99999> < < endl;
}
[解决办法]
循环用递归代替
if用 ? : 代替
[解决办法]
除了用递归模板，干脆用穷举法得了，10001-99999，最后判断用个函数，比如：
bool IsEqual( int a, int b )
{
return (a==b);
}
肯定行，
如果想再好些，就先做些逻辑推理，实在没法就穷举剩余的部分。
[解决办法]
arong1234() ( ) 厉害
为更好理解，并考虑无解的情况,偶改一下：）
#define MULNUM 4
int result(int i)
{
int a,b,c,d,e;
int iMul,iMul1;
a = ( i / 10000 ) % 10;
b = ( i / 1000) % 10;
c = ( i / 100 ) % 10;
d = ( i / 10 ) % 10;
e = i % 10;
iMul = e * 10000 + d * 1000 + c * 100 + b * 10 + a ;
iMul1 = i * MULNUM;
return (i> 10000 && iMul1 == iMul && a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c!=e
&& d != e) || i <= 10000 ?(i):( result(i-1));
}
#include <iostream>
using namespace std;
int main()
{
cout < < result(25000) < < endl;
}
[解决办法]
这里还有个问题,如果是有重复的或者是无结果呢 ? 怎么让递归终止?
freshui(五月的风 -最近老犯困)
strlen(srcNum)> 5? return : (nop); //退出条件
这么退出好象不行, 因为return 语句无法这么使用
而其他人就是得出一个答案就不再继续
[解决办法]
解题思路：
正常的话只要if/for就可以解决问题，for,while,if,switch不能用，那可以用其他来模拟if/for就可以。if可以用 "?: "加上内部类(对C++就是函数指针)来模拟，for可以用递归模拟。
另外：
E-> A
E,D-> B 因此只要穷举EDC，验证ABCDE是否互不相等就可以。
代码如下(java6.1通过)：
import java.lang.Math;
public class test {
// 抽象语句类
abstract class Statement {
protected int A,B,C,D,E;
abstract void Execute();
public void Assign(Statement s) {
A=s.A;
B=s.B;
C=s.C;
D=s.D;
E=s.E;
}
}
// 空操作语句
class ST_NOP extends Statement {
public void Execute() {
return;
}
}
//
class ST_PrintABCDE extends Statement {
public void Execute() {
System.out.print(A);
System.out.print(B);
System.out.print(C);
System.out.print(D);
System.out.println(E);
}
}
//
class ST_FindABCDE extends Statement {
//
class ST_NextCDE extends Statement {
public void Execute() {
Statement s1=new ST_NextC();
s1.Assign(this);
Statement s2=new ST_NextDE();
s2.Assign(this);
Statement s=(C <9) ? s1 : s2;
s.Execute();
Assign(s);
}
}
//
class ST_NextDE extends Statement {
public void Execute() {
Statement s1=new ST_NextD();
s1.Assign(this);
Statement s2=new ST_NextE();
s2.Assign(this);
Statement s=(D <9) ? s1 : s2;
s.Execute();
Assign(s);
}
}
//
class ST_NextD extends Statement {
public void Execute() {
C=1;
D++;
}
}
//
class ST_NextE extends Statement {
public void Execute() {
C=1;
D=1;
E++;
}
}
//
class ST_NextC extends Statement {
public void Execute() {
C++;
}
}
// 根据E计算A
private void CalculateA() {
A=(E*4)%10;
}
//
private void CalculateB() {
B=((D*4)%10+(E*4)/10)%10;
}
//
private void NextCDE() {
Statement s=new ST_NextCDE();
s.Assign(this);
s.Execute();
Assign(s);
}
// 验证ABCDE互不相等
private Statement Validate() {
CalculateA();
CalculateB();
Statement s1=new ST_PrintABCDE();
s1.Assign(this);
Statement s2=new ST_FindABCDE();
s2.Assign(this);
double X=(A*Math.pow(10,4)+B*Math.pow(10,3)+C*Math.pow(10,2)+D*10+E)*4;
double Y=(E*Math.pow(10,4)+D*Math.pow(10,3)+C*Math.pow(10,2)+B*10+A);
boolean b=(Math.round(X)==Math.round(Y));
return test.fn_IF(b,s1,s2);
};
//
public void Execute() {
NextCDE();
Validate().Execute();
}
}
// 模拟IF语句
static Statement fn_IF(boolean b, Statement s1, Statement s2) {
return b ? s1 : s2;
}
//
public void findABCDE() {
Statement s=new ST_FindABCDE();
s.E=1;
s.D=1;
s.C=0;
s.Execute();
}
//
public static void main(String a[]) {
new test().findABCDE();
}
}
后记：完成后发现比初想的复杂很多。
[解决办法]
细看一下,arong1234()已经给出答案,简洁高效,学习了.
但都没解决无解退出递归的问题.
我的代码虽复杂,但设计上考虑到扩展.现在给出解决递归退出的代码.
import java.lang.Math;
public class test {
// 抽象语句类
abstract class Statement {
protected int A,B,C,D,E;
abstract void Execute();
public void Assign(Statement s) {
A=s.A;
B=s.B;
C=s.C;
D=s.D;
E=s.E;
}
}
// 空操作语句
class ST_NOP extends Statement {
public void Execute() {
System.out.print( "NO SOLUSION! ");
}
}
//
class ST_PrintABCDE extends Statement {
public void Execute() {
System.out.print(A);
System.out.print(B);
System.out.print(C);
System.out.print(D);
System.out.println(E);
}
}
//
class ST_FindABCDE extends Statement {
//
class ST_NextCDE extends Statement {
public void Execute() {
Statement s1=new ST_NextC();
s1.Assign(this);
Statement s2=new ST_NextDE();
s2.Assign(this);
Statement s=(C <9) ? s1 : s2;
s.Execute();
Assign(s);
}
}
//
class ST_NextDE extends Statement {
public void Execute() {
Statement s1=new ST_NextD();
s1.Assign(this);
Statement s2=new ST_NextE();
s2.Assign(this);
Statement s=(D <9) ? s1 : s2;
s.Execute();
Assign(s);
}
}
//
class ST_NextD extends Statement {
public void Execute() {
C=1;
D++;
}
}
//
class ST_NextE extends Statement {
public void Execute() {
C=1;
D=1;
E++;
}
}
//
class ST_NextC extends Statement {
public void Execute() {
C++;
}
}
//
private void NextCDE() {
Statement s=new ST_NextCDE();
s.Assign(this);
s.Execute();
Assign(s);
}
//
class ST_ValidABCDE extends Statement {
// 根据E计算A
private void CalculateA() {
A=(E*4)%10;
}
// 根据E,D计算B
private void CalculateB() {
B=((D*4)%10+(E*4)/10)%10;
}
//
public void Execute() {
CalculateA();
CalculateB();
Statement s1=new ST_PrintABCDE();
s1.Assign(this);
Statement s2=new ST_FindABCDE();
s2.Assign(this);
int X=(A*10000+B*1000+C*100+D*10+E)*4;
int Y=(E*10000+D*1000+C*100+B*10+A);
boolean b=(X==Y);
Statement s=test.fn_IF(b,s1,s2);
s.Execute();
}
}
// 验证ABCDE
private void Validate() {
Statement s1=new ST_NOP();
s1.Assign(this);
Statement s2=new ST_ValidABCDE();
s2.Assign(this);
boolean b=(E> 9);
Statement s=test.fn_IF(b,s1,s2);
s.Execute();
};
//
public void Execute() {
NextCDE();
Validate();
}
}
// 模拟IF语句
static Statement fn_IF(boolean b, Statement s1, Statement s2) {
return b ? s1 : s2;
}
//
public void findABCDE() {
Statement s=new ST_FindABCDE();
s.E=1;
s.D=1;
s.C=0;
s.Execute();
}
//
public static void main(String a[]) {
new test().findABCDE();
}
}
jdk6.1测试 1.ABCDE*4=EDCBA
2.ABCDE*5=EDCBA
通过.
[解决办法]
如果大家一定要确保有无解退出的解，如下
template <int i>
int result()
{
return ((i> =10000 && i*4==(10000*(i%10) + 1000*((i/10)%10)) + 100*((i/100)%10))+10*((i/1000)%10)) + ((i/10000)%10)))?(i):(template sum <i-1> ()));
}
#include <iostream>
using namespace std;
int main()
{
int iResult = result <30000> ;
cout < < (iResult > = 10000)?(iResult):( "no such number ")) < < endl;
}
