Question

USE JAVA, PYTHON OR C TO WRITE AN ALGORITHM FOR THIS EXERCISE:

. Chocolate bar puzzle Given an n × m chocolate bar, you need to break it into nm 1 × 1 pieces. You can break a bar only in a straight line, and only one bar can be broken at a time. Design an algorithm that solves the problem with the minimum number of bar breaks. What is this minimum number? Justify your answer by using the properties of a binary tree.

NOTE: I NEED A CODE FOR THIS EXERCISE WRITTEN IN ANY LANGUAGE.

Answer 1

//To cut the n x m chocolate bar into nm 1x1 pieces, we need minimum mn-1 cuts. The code is shown below :

#include <stdio.h>
int main()
{
   int m,n;
   long ans;
   printf("Enter the value of m :");
   scanf("%d",&m);
   printf("Enter the value of n :");
   scanf("%d",&n);
  
   ans = m*n-1;
   printf("Cuts required to break a %dx%d choco bar into 1x1 bars = %ld\n",m,n,ans);
}

#include <stdio.h> int main() { int m, n; long ans; printf("Enter the value of m :"); scanf("%d",&m); printf("Enter the value of n :"); scanf("%d",&n); ans = m*n-1; printf("Cuts required to break a %dx%d choco bar into 1x1 bars = %ld\n",m, n, ans); }

You can save the file as filename.c which can be compiled using "cc filename.c". You can run it using "./a.out".

Two sample outputs are shown below :

Enter the value of m :10 Enter the value of n :1 Cuts required to break a 10x1 choco bar into 1x1 bars = 9

Enter the value of m:5 Enter the value of n :3 Cuts required to break a 5x3 choco bar into 1x1 bars = 14

How to arrive at this logic ? Note that we can cut one bar at a time. Each cut increases the total number of bars by 1. To get mn pieces we need mn-1 cuts.