首页 > 试题广场 >

小东分苹果

[编程题]小东分苹果

热度指数：13153 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

给定一个整数n，表示熊的头数

输出描述:

返回最初的苹果数。保证有解。

示例1

输入

输出

算法知识视频讲解

drdr

遇到这样的题目还是得仔细推演一下，
我的是直接模拟法。
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)

cycleof

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)

pein531

苹果数从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)

Python

TimeMac

从后往前推，知道为什么小熊数量有限制了，上了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)

C/C++

nbgao

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)

goeatit

数学王子们的解答会非常简洁，直接 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)

CrazyCodingGirl

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)

HelloWorldn

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

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)

洋气的Camille

如果知道最后一个熊的每份苹果有几个，反向可以推出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)

fight灬奋斗

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)

Java

QunQuan

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)

ZhanHeng

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)

麻夹电甜zgb

搞不懂啊，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)

Wolsen

设苹果总数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)

牛客103647号

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)

StudyOfSlagD

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)