算法题

Question

给定一个数字n,如果n是偶数就让n/2，如果是奇数就让n +1或-1，例
n = 31;
n = n - 1; //30
n = n / 2; //15
n = n + 1; //16
n = n / 2; //8
n = n / 2; //4
n = n / 2; //2
n = n / 2; //1
问：怎样能够以最少的计算次数，算出n = 1;

Answer 1

int i = the original number;
So it's clear that:  Math.pow(2, m) < i < Math.pow(2, n);  //m < n
So get the most quick way to find m or n, you can find the most quick way to 1.
结帖率：0.00%           

Answer 2

n = 31; 
while(n != 1){
    if(n % 2 == 1){
        n--;
    }else{
        n = m / 2;
    }
}

Answer 3

int count;  //the number of steps31 - 1 = 30; //count = 1
30 / 2 = 15; //count = 2
15 - 1 = 14; //count = 3
14 / 2 = 7;  //count = 4
7  - 1 = 6;  //count = 5
6  / 2 = 3;  //count = 6
3  - 1 = 2;  //count = 7
2  / 2 = 1;  //count = 831 + 1 = 32; //count = 1
32 / 2 = 16; //count = 2
16 / 2 = 8;  //count = 3
8  / 2 = 4;  //count = 4
4  / 2 = 2;  //count = 5
2  / 2 = 1;  //count = 6
So your solution is not the best one...

Answer 4

So I think the best way is:1. find the m and n;  // actually, m = n + 1
2. count the steps 'i' to find m, and 'j' to find n;
3. if i > j + 1, the best step is: j + n
   else, the best step is: m + i

Answer 5

不知道这样可以么？public class Test1 {    public static void main(String[] args) {
        int n = 31;
        
        if(n < 1) {
            return;
        }
        int count = 0;        
        while(n != 1) {            
            if(n % 2 == 0) {
                n /= 2;                
            } else {
                if((n & 2) == 0 || n == 3) {
                    n--;
                } else {
                    n++;
                }
            }
            count++;
            System.out.println(count + ": " + n);
        }
        System.out.println("Total: " + count);
    }
}

Answer 6

1: 32
2: 16
3: 8
4: 4
5: 2
6: 1
Total: 6

Answer 7

(n & 2) == 0   是什么意思？

Answer 8

...
kan kan n neng bu neng bei 2 zheng chu...

Answer 9

9#    I am wrong...Sorry...

Answer 10

那 (n & 2) 与 (n % 2) 有什么区别 

Answer 11

n & 2 == 0 is to detect the second bit whether 1 or 0...

Answer 12

已通过验证：
import java.util.*;
public class Test
{
public static ArrayList<Integer> list=new ArrayList<Integer>();
public static int num=17;
public static boolean flag=false;
public static void main(String[] args) throws Exception
{
Quick(num);
}
public static void Quick(int n)
{
list.add(n);
if(n==1)
{
System.out.println(list);
System.exit(0);
}
if(n%2==0)
{
Quick(n/2);
}
else
{
if(flag==false)
{
flag=true;
}
else
{
list.clear();
if(num%2==1)
{
list.add(num);
Quick(num+1);
}
else
{
list.add(num);
list.add(num/2);
Quick(num/2-1);
}
}
Quick(n-1);
Quick(n+1);
}
}
}
总的思路就是：在给定数字到1之间奇数只能出现一次（包括给定数字，不包括1）；
如31-30-15(不行，因为31和15都是奇数，再现了两次）

Answer 13

n & 2) == 0 || n == 3
这一句不是太明白,能否帮忙理解一下

Answer 14

哦 做奇数的加减法，是要保证这个奇数的二进制数末两位为00，这样下两次计算就一定会是除法，但3比较特殊直接-1就可，明白了这个(n & 2) == 0判断的真正含义。

Answer 15

[size=30px]o(∩_∩)o[/size]

Answer 16

This problem looks so familiar. Is it from ACM Problem Set?Anyway, I tried to create this program using Dynamic Programming. Please help me to verify. Thanks.
public class ApproachingOne { public static void main(String[] args) {
switch (args.length) {
     case 1: 
     try 
     {
     int n = Integer.parseInt(args[0]);
     if (n > 0)
     {
     approachingOne(n);
     }
     else printUsage();
     }
     catch (Exception e)
     {
     e.printStackTrace();
     printUsage();
     }
     break;
     default : printUsage();
     }
} private static void approachingOne(int n) {
Node[] nodes = new Node[n+1];
for (int i=n+1; i>0; i--)
{
nodes[i-1] = new Node(i);
}

for (int i=0; i<n+1; i++)
{
Node node = nodes[i];
int element = node.getElement();

if (element == 1) // Do nothing
{}
else if ((element & 1) > 0) // Odd number, check left & right Node
{
Node leftNode = nodes[i-1];
node.setParent(leftNode);
node.setSteps(leftNode.getSteps()+1);
node.setOperation(" - 1 ");

if (i < n)
{
Node rightNode = nodes[i+1];
if (rightNode.getParent() != null && (rightNode.getSteps() < leftNode.getSteps()))
{
node.setParent(rightNode);
node.setSteps(rightNode.getSteps()+1);
node.setOperation(" + 1 ");
}
}
}
//Even numbers are updated.

// Update current node's double node if needed.
if (2 * i < n) // Simplified form of (2 * (n + 1) <= (n + 1))
{
Node doubleNode = nodes[2 * i + 1];
doubleNode.setParent(node);
doubleNode.setSteps(node.getSteps()+1);
doubleNode.setOperation(" / 2 ");
}
}

Node targetNode = nodes[n-1];
int steps = 0;
while (targetNode.getParent() != null)
{
Node parentNode = targetNode.getParent();
System.out.println(targetNode.getElement() + targetNode.getOperation() + "= " + parentNode.getElement());
targetNode = parentNode;
steps++;
}
System.out.println("Total Steps: " + steps);
} private static void printUsage() {
     System.out.println("Approaching One Testing Program");
     System.out.println("Usage:");
     System.out.println("java ApproachingOne <n>");
     System.out.println("\tn\tGiven positive integer.");
     System.out.println("\t \tIf n is Even, move to n/2;");
     System.out.println("\t \tElse, move to either n+1 or n-1;");
     System.out.println("\t \tStop when n is equal to 1.");
}

static class Node
{
private int element;
private int steps;
private Node parent;
private String operation;

public Node(int e)
{
this.element = e;
this.steps = 0;
this.parent = null;
this.operation = "";
} public int getElement() {
return element;
} public void setElement(int element) {
this.element = element;
} public int getSteps() {
return steps;
} public void setSteps(int steps) {
this.steps = steps;
} public Node getParent() {
return parent;
} public void setParent(Node parent) {
this.parent = parent;
} public String getOperation() {
return operation;
} public void setOperation(String operation) {
this.operation = operation;
}
}
}

Answer 17

Here are some testing results.
bin>java ApproachingOne 1
Total Steps: 0bin>java ApproachingOne 2
2 / 2 = 1
Total Steps: 1bin>java ApproachingOne 3
3 - 1 = 2
2 / 2 = 1
Total Steps: 2bin>java ApproachingOne 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 2bin>java ApproachingOne 5
5 - 1 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 3bin>java ApproachingOne 6
6 / 2 = 3
3 - 1 = 2
2 / 2 = 1
Total Steps: 3bin>java ApproachingOne 7
7 - 1 = 6
6 / 2 = 3
3 - 1 = 2
2 / 2 = 1
Total Steps: 4bin>java ApproachingOne 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 3bin>java ApproachingOne 9
9 - 1 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 4bin>java ApproachingOne 10
10 / 2 = 5
5 - 1 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 4bin>java ApproachingOne 11
11 - 1 = 10
10 / 2 = 5
5 - 1 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 5bin>java ApproachingOne 12
12 / 2 = 6
6 / 2 = 3
3 - 1 = 2
2 / 2 = 1
Total Steps: 4bin>java ApproachingOne 13
13 - 1 = 12
12 / 2 = 6
6 / 2 = 3
3 - 1 = 2
2 / 2 = 1
Total Steps: 5bin>java ApproachingOne 14
14 / 2 = 7
7 - 1 = 6
6 / 2 = 3
3 - 1 = 2
2 / 2 = 1
Total Steps: 5bin>java ApproachingOne 15
15 + 1 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 5bin>java ApproachingOne 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 4bin>java ApproachingOne 17
17 - 1 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 5bin>java ApproachingOne 18
18 / 2 = 9
9 - 1 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 5bin>java ApproachingOne 19
19 - 1 = 18
18 / 2 = 9
9 - 1 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 6bin>java ApproachingOne 20
20 / 2 = 10
10 / 2 = 5
5 - 1 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 5bin>java ApproachingOne 30
30 / 2 = 15
15 + 1 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 6bin>java ApproachingOne 31
31 + 1 = 32
32 / 2 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 6bin>java ApproachingOne 32
32 / 2 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Total Steps: 5

Answer 18

Well, I used Dynamic Programming to solve this problem.It'd be good if you could find an algorithm to solve it without using DP.:-)

Answer 19

我的思路是这样，要计算n
n=p+q；
其中p为所有小于n的2的幂当中最大者
也就是说，把n分成两部分，一部分是2的幂，这部分只要一直除以2就可以不断减小，另一部分是导致计算过程出现+1或-1的部分，它在计算到某一步的时候就会出现奇数而这样分开之后，q可以继续再分下去（只要它不是1），这样计算n需要的步骤数就是计算p的步骤数和计算q的步骤数两者较大者，有可能还要+1（如果p和q两部分同时到1，那么1+1=2，还需要一步来变成1）

Answer 20

I think I've found one algorithm.
I am testing it now. If it works well, I will post my code here.

Answer 21

This one is damn interesting.
public class ApproachingOneSecondTry {
public static void main(String[] args) {
switch (args.length) {
     case 1: 
     try 
     {
     int n = Integer.parseInt(args[0]);
     if (n > 0)
     {
     approachingOne(n);
     }
     else printUsage();
     }
     catch (Exception e)
     {
     e.printStackTrace();
     printUsage();
     }
     break;
     default : printUsage();
     }
} private static void approachingOne(int n) {
int steps = 0;
while (n > 1)
{
if ((n & 1) == 0)
{
System.out.println(n + " / 2 = " + (n >>= 1));
steps++;
}
else if ((n & 7) < 7)
{
System.out.println(n + " - 1 = " + (n -= 1));
steps++;
}
else
{
System.out.println(n + " + 1 = " + (++n));
steps++;
}
}
System.out.println("Total Steps: " + steps);
} private static void printUsage() {
     System.out.println("Approaching One Testing Program");
     System.out.println("Usage:");
     System.out.println("java ApproachingOneSecondTry <n>");
     System.out.println("\tn\tGiven positive integer.");
     System.out.println("\t \tIf n is Even, move to n/2;");
     System.out.println("\t \tElse, move to either n+1 or n-1;");
     System.out.println("\t \tStop when n is equal to 1.");
}
}

Answer 22

由二进制数给我们的启发,这道题有点简单的动态规划的意思.
这个问题的主要操作在对奇数的处理上,即每当是奇数的时候,需要动态的判断+1好还是-1好的问题.
对于在数列:0,2,4,8,16,32,....POW(n)上的数仅进行除2就可以得到(n=1),即这时需要的操作是最少的.
所以,我们在对+1,-1进行选择时,应该选择能使n回归到上面的那个数列上的操作.算法如下:
 while(n!=1){
     if(n%2==1){
        if(n+1 is 2的幂){
   n=n+1;
        }esle{
  n=n-1；
        }
     }esle{
        n=n/2;
     }
}

Answer 23

实现如何判断n+1是不是2的幂
for(i=1 to 1000)
 if (2^i<n) then i=i+1
把i作为上面程序中的指数,在n=n+1后面加上n=n-1;