首页 > 试题广场 >

小东分苹果

[编程题]小东分苹果
  • 热度指数:13051 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

果园里有一堆苹果,一共n头(n大于1小于8)熊来分,第一头为小东,它把苹果均分n份后,多出了一个,它扔掉了这一个,拿走了自己的一份苹果,接着第二头熊重复这一过程,即先均分n份,扔掉一个然后拿走一份,以此类推直到最后一头熊都是这样(最后一头熊扔掉后可以拿走0个,也算是n份均分)。问最初这堆苹果最少有多少个?


输入描述:
给定一个整数n,表示熊的头数


输出描述:
返回最初的苹果数。保证有解。
示例1

输入

2

输出

3
遇到这样的题目还是得仔细推演一下,
我的是直接模拟法。
class Apples {
public:
    
    int getInitial(int n) {
        // write code here		
        int ret;
        for(ret = n + 1; ; ret += n){
            int cnt = 1;
  		    int tmp = (n-1)*(ret/n);
            while(tmp%n==1){
                cnt++;
                tmp = (n-1)*(tmp/n);
                if(cnt==n) return ret;
            }
        }  
    }
};

编辑于 2017-04-26 14:11:06 回复(2)
设这堆桃子至少有x个,借给它们4个,成为x+4个。5个猴子分别拿了a,b,c,d,e个桃子(其中包括吃掉的一个桃子),则可得
a=(x+4)/5,b=4(x+4)/25,c=16(x+4)/125,d=64(x+4)/625,e=256(x+4)/3125    
e应为整数,而256不能被5整除,所以(x+4)应该是3125的倍数,所以(x+4)=3125k(k为自然数)。当k =1时,x=3121
所以,5个猴子至少摘了3121个桃子

(3121-1)/5*4=2496(个) (2496-1)/5*4=1996(个) (1996-1)/5*4=1596(个)
(1596-1)/5*4=1276(个) (1276-1)/5*4=1020(个)
所以最后剩下1020个

所以 n个熊的时候就是 n^n-(n-1)...


发表于 2015-11-10 20:45:09 回复(3)
class Apples {
public:
    int getInitial(int n) {
        int sum,i,j;
        for(i=0;i<1000000;i++){
            sum = (n-1)*i;
            for(j=0;j<n;j++){
                if(sum%(n-1) != 0)
                    break;
                else
                	sum = sum/(n-1)*n + 1;
            }
            if(j == n)
                break;
        }
        return sum;
    }
};

发表于 2017-07-18 17:31:41 回复(1)
苹果数从n+1开始尝试,看是否能够满足每次都能去掉一个苹果还可以均分为n份,如果不能,就尝试下一个数,第一个满足的数就是要求的最少苹果数。
import java.util.*;

public class Apples {
    public int getInitial(int n) {
        // write code here
        int start = n + 1;     // 从n+1开始尝试
        while(true){
            if(judge(start, n)) break;
            start ++;
        }
        return start;
    }
    
    private boolean judge(int apples, int n) {
        int bears = n;
        while(bears > 0){
            // 要保证每次扔掉一个苹果之后剩下的都能均分为n份
            if(apples % n == 1){
                apples -= 1 + apples / n;
                // 有一个熊已经分完了
                bears --;
            }else
                return false;
        }
        // 是否所有的熊都分到了
        return bears == 0;
    }
}


发表于 2021-02-23 14:56:45 回复(0)
import java.util.*;

public class Apples {
    public int getInitial(int n) {
        // write code here
        int num = 1-n;
        while (true) {
            num += n;
            boolean f = false;
            int num1 = num;
            for (int i = 2; i <= n; i++) {
                if (num1 % (n-1) != 0) {
                    f = true;
                    break;
                }
                num1 = num1 * n / (n-1) + 1;
            }
            if (!f) return num1;
        }
    }
}

发表于 2020-08-19 16:56:54 回复(0)

从后往前推,知道为什么小熊数量有限制了,上了9个后花了十几秒...

class Apples:
    def getInitial(self, n):
        if n == 2:
            return 3
        else:
            begin = 1              #如果不是2个小熊,那么最后一个小熊最少得到一个,初始化从1开始
            b = 0
            while True:
                res = begin * n + 1
                for i in range(n-1):
                    a,b = divmod(res,n-1)
                    if b != 0:
                        break
                    res = a*n + 1    #余数一直为零才符合要求
                if b != 0:
                    begin += 1
                else:
                    return res
编辑于 2018-10-19 22:46:00 回复(0)
class Apples {
public:
    int getInitial(int n) {
        int r;         for(r=n+1;;r+=n)         {             int k = 1;             int t = (n-1)*(r/n);             while(t%n==1)             {                 k++;                 t = (n-1)*(t/n);                 if(k==n)                     return r;             }         }
    }
};

发表于 2017-11-06 13:54:32 回复(0)
数学王子们的解答会非常简洁,直接 return (n ** n - n + 1).
然而我:
class Apples:
    def getInitial(self, n):
        flag = True
        x_0 = n
        while flag:
            x_0 = x_0 + 1
            x = x_0
            i = 1
            while (i < (n + 1)):
                if (x % n == 1):
                    x = x - 1 - (x - 1) / n
                    i = i + 1
                    if (i == (n + 1)):
                        flag = False
                else:
                    break
        return x_0
只能模拟这个过程。遍历,从总苹果数x_0 = n + 1开始,若x_0满足每次求余得1,则返回x_0,
否则x_0 = x_0 + 1 继续这个过程,直到找到满足条件的x_0为止。

发表于 2017-07-19 15:41:45 回复(0)
class Apples {
public:
    int getInitial(int n) {
    int x = n;
	while (++x)
	{
		int temp = x;
		for (int i = 0; i < n; i++)
		{
			if ((temp - 1) % n == 0)
				temp = (temp - 1) / n*(n - 1);
			else
				break;
			if (i == n - 1)
				return x;
		}
	}
        return x;
    }
};

发表于 2017-06-18 14:55:18 回复(0)

很多高票的答案都有问题,老老实实用暴力法。

public int getInitial(int n) {
        //return n*n-n+1;
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            int count = i;
            boolean flag = false;
            for (int j = 1; j <= n; j++) {
                count--;
                if (count % n == 0){
                    count = count / n *(n-1);
                } else {
                    flag = true;
                    break;
                }
            }
            if(!flag){
                return i;
            }
        }
        return 0;
    }
编辑于 2017-01-03 22:42:36 回复(0)
如果知道最后一个熊的每份苹果有几个,反向可以推出n个熊能分多少苹果。但由于最后一个熊每份有几个苹果未知,所以从0开始试,最初得到可行解时,返回。
class Apples {
public:
    int getInitial(int n) {
        // write code here
        //x为每份苹果的数量,m为苹果总数,k从最后一个熊开始向前
        int k, x, m;
        for (int i = 0; ; ++i) {
            k = 1;
            x = i;
            m = n*x+1;
            while (k < n) {
                if (m >= n-1 && m%(n-1) == 0) {
                    x = m/(n-1);
                    m = n*x+1;
                    ++k;
                } else
                    break;
            }
            if (k == n)
                return m;
            if (k != n)
                continue;
            
        }
        return m;
    }
};
i表示从0开始,不断尝试最后一个小熊每份苹果的数量;
k表示从后往前,第k个小熊时的情况;
x表示当前每份的苹果数量,m表示当前总数量,都可由下一个熊倒推得到。
当x为正整数时,说明当前i可用,继续反推;否则,跳出while循环,如果已推至第一个小熊,返回结果;否则,尝试下一个i。
发表于 2016-09-05 16:53:43 回复(0)
class Apples {
public:
    int getInitial(int n) {
        int i=0,R,k,flag=1;
        while(flag){
            while((i*n+1)%(n-1))
                i++;
            R=n*i+1;//最后一头熊没扔之前可能剩下的苹果数;
            k=n;
            while(k>1&&R%(n-1)==0){//R%(n-1)==0判断剩下的苹果数是否合法
                R=R/(n-1)*n+1;//逆序推前一头熊没扔之前剩下的苹果数;
                k--;
            }
            if(k==1)
                flag=0;
            i++;
        }
        return R;
	}
};
编辑于 2016-09-03 10:29:28 回复(0)
//只能遍历了,从1,n+1,2n+1,3n+1开始
class Apples {
public:
    bool IsValid(int shu, int n)
    {
        int cc=n;
        while(shu%n == 1)
        {
            cc--;
            if(!cc)
                return true;
            shu = shu -shu/n-1;
        }
        return false;
   }
    int getInitial(int n) {
        // write code here
        int cc=0;
		while(1)
		{
			if(IsValid(cc*n+1,n))
			{
                return cc*n+1;
			}
			cc++;
		}
    }
};

发表于 2016-08-18 00:16:44 回复(0)
import java.util.*;
public class Apples {
    public int getInitial(int n) {
        int init=0,k,i,next=0,result;
        while(true){
            k=init;
            for(i=1; i<n; i++){
                next = k*n+1;
                if(next%(n-1)==0){
                   k=next/(n-1); 
                }
                else{
                    init++;
                    break;
                }
            }
            if(i==n){
                result = k*n+1;
                break;
            }
        }
        return result;
    }
}
 init   is the apples the last bear got;
k   is the next bear got; 
i   is the number of bear i=1 means the last bear;
next   is when the # i   bear  come, how many  apples in the heap.
发表于 2016-07-21 20:01:26 回复(0)
import java.util.*;
//思想:经过一番推理之后就是一个数学公式,从一般到特殊。
//3个熊(X为苹果数) 要求 [2/3]^3 *(x+2)-3 为整数,那么x+2=3^3,x=3^3-2
//N个熊,则x=n^n-(n-1)=n^n-n+1
public class Apples {
    public int getInitial(int n) {
        int result=(int)Math.pow(n,n)-n+1;
        return result;
    }
}

发表于 2016-04-03 22:42:41 回复(0)
搞不懂啊,3头熊为什么是25个,
25,被第一头拿了后剩下  16个吧,然后第二个熊拿完了 剩下 10个,第三个熊拿完了不是还剩下6个么
发表于 2017-10-29 19:42:58 回复(1)
classApples
{
public:
    intgetInitial(intn)
    {
        intresult = 0;
        for(inti = 1; true; i++)
        {
            result = i;
            bool flag = false;
               //cout << "i = "<< i << endl;
            for(intj = 0; j < n; j++)
            {
                //cout << "result = " << result << endl;
                if(result > 0&& (result - 1) % n == 0)
                {
                    result = (result - 1)*(n - 1)/n;
                    flag = true;
                } else
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                returni;
        }
        returnresult;
    }
};
需要说明一下的是,由于不知道最少是几个,我从数学上也推不出来规律,干脆我就采用遍历的方式求解了;
从拥有的苹果总数,从1开始遍历,知道找到符合分苹果规律的数目为止;
其中if语句是保证在最后一次分苹果之前,苹果的个数不为零,并且苹果的总数减1符合n的倍数,即可以分成n份,否则该数字就是不符合要求的。
ps:为什么我保存之后,代码的格式变得好难看。。。行之间的距离变得特别的大

编辑于 2015-10-11 20:16:41 回复(2)
设苹果总数x, 由题意知(x+n-1) 可被n 整除,  第一只熊分到 (x+n-1)/n只苹果(分到的+扔掉的)。  此时还剩下(n-1)(x+n-1)/n 只苹果。 第二只熊分得 (n-1)(x+n-1)/n^2 只苹果(分到的+扔掉的),    依次类推   ……    最后一只熊(分到+扔掉)K= (n-1)^(n-1)(x+n-1)/n^n  只苹果。K 为自然数,故分子必须是n^n的倍数。  由于(n-1)^(n-1) 与 n^n 互质, 则必有 (x+n-1) = t * n^n 。显然 t 取 1 时x 最小, x= n^n -n+1。
发表于 2016-03-23 16:25:35 回复(40)
public class Apple {
	 public static int getInitial(int n) {
		 for(int i=n+1;;i++) {
			 int temp=i;
			 int bear=n;
			 while(bear>0) {
				 
				 if(temp%n==1){
					 temp=temp-temp/n-1;
					 bear--;
				 }else {
					 break;
				 }
				 
			 }
			 if(bear==0) {
				 return i; 
			 }
		 }
	 }
	 public static void main(String[] args){
		System.out.println(getInitial(2));
	 }
}
无法从后往前推,因为最后一个熊拿到的个数是不确定的,所以就使用遍历,从n+1开始,判断在每一次的加减的过程中,该数是否对n取余等于1,如果是则继续减,直到熊的个数等于0为止,否则就进入下一个数的判断。
发表于 2015-10-12 10:44:21 回复(16)
import java.util.*;
/**思路:因为每次分n堆都会多出来1个,所以我们借给熊n-1个,以致每次都可以刚好分成n堆*/
public class Apples {
    public int getInitial(int n) {
         long a = (long)Math.pow(n, n);
        return (int)a-n+1;
    }
}

发表于 2016-09-09 13:26:58 回复(3)