KEMBAR78
PDS Lab Ass5 | PDF | Function (Mathematics) | Mathematics
Scribd
Upload
86 views2 pages

PDS Lab Ass5

The document provides instructions for an assignment on 2D arrays and recursion. It contains two parts: 1. Write a function to check if queens are placed safely on a chessboard without attacking each other, and a program to input queen positions and call the function. 2. Write recursive functions to: a) Count the non-repeated partitions of a number. b) Print all non-repeated partitions of a number by choosing summands in descending order and passing the current array of summands. The main function should take input and call the above functions to solve the problems.

Uploaded by

Tumpy Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
86 views2 pages

PDS Lab Ass5

The document provides instructions for an assignment on 2D arrays and recursion. It contains two parts: 1. Write a function to check if queens are placed safely on a chessboard without attacking each other, and a program to input queen positions and call the function. 2. Write recursive functions to: a) Count the non-repeated partitions of a number. b) Print all non-repeated partitions of a number by choosing summands in descending order and passing the current array of summands. The main function should take input and call the above functions to solve the problems.

Uploaded by

Tumpy Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Indian Institute of Technology, Kharagpur

CS19001 Programming and Data Structures Laboratory, Section 10, Spring 2023
Assignment 5: 2D Array, Recursion (May 2, 2023)

INSTRUCTIONS :
• Name your file as <roll_no>_5A.c for Part 1 and <roll_no>_5B.c for Part 2.
• Write your name, roll number, and assignment number at the beginning of your program.

1. (8 marks) Two queens in a chessboard can attack each other if they share the same row,
column, or diagonal.
(a) (5 marks) Write a function queensaresafe( ) that takes as input a 2-dimensional array
of characters and the value of n. The elements of the n × n board are ’q’ or ’.’. ’q’s
represent queens, ’.’s represent open spaces. The function returns 1 if the queens do
not attack each other, and 0 otherwise,
int queensaresafe (char board[][20], int n)
(b) (3 marks) Write a C program which declares a 20 × 20 2-D array, and takes as input
from the user the value of n, the size of the chessboard. It then takes as input the
positions of n queens, as (rowno, colno). It constructs the array based on the user’s
inputs by filling up the relevant entries with ’q’ or ’.’. and then calls the above function
to determine if the chess board represented by the board is one where the queens are
non-attacking. Print the result.

2. A partition of a positive integer n, also called an integer partition, is a way of writing n


as a sum of positive integers. Two sums that differ only in the order of their summands
are considered the same partition. We are interested in partitions that does not repeat
summands.
For example, 4 can be partitioned in five distinct ways but only in two ways if the partitions
are non-repeating. 6 has four non-repeating partitions.

All partitions Non-repeating partitions Non-reepating partitions


of 4 of 4 of 6
4 4 6
3+1 3+1 5+1
2+2 4+2
2+1+1 3+2+1
1+1+1+1

(a) (6 marks) Write a recursive function to count the non-repeated partitions of a give
number n.
Hint: In order to avoid repetitions, you may choose the summands in descending order.
That is, for n = 6, if 6 and 5 are already chosen as the previous summands, the next
summand must be less than 5. Pass two arguments to your recursive function. The first
stands for the amount remaining to be balanced by summands and the second stands for
the smallest summand chosen so far. Recursion stops when the first argument becomes
0. Here is a possible prototype for the function.
int countpartitions (int remaining, int curchoice) ;
(b) (4 marks) Write a function to print all non-repeated partitions of a positive integer n.
Store in an array all summands chosen so far. A recursive call is made after a new
summand is chosen. Append this summand to the array and pass the appended array
to the recursive call. When the recursion ends (i.e., remaining becomes zero), print
the summand stored in the array one by one from beginning to end. You may return
the total number of partitions.
int partition (int remaining, int curchoice, int prefix[], int sizeprefix) ;
(c) (2 marks) Write a main function that takes input form the user and calls the above
functions.

Page 2

You might also like