考虑一个特殊的工程师和医生家族,遵循以下规则:
null
- 每个人都有两个孩子。
- 工程师的第一个孩子是工程师,第二个孩子是医生。
- 医生的第一个孩子是医生,第二个孩子是工程师。
- 历代医生和工程师都是从工程师开始的。
我们可以用下图来表示情况:
E / E D / / E D D E / / / / E D D E D E E D
在上面的祖先树中给定一个人的等级和位置,找到此人的职业。 例如:
Input : level = 4, pos = 2Output : DoctorInput : level = 3, pos = 4Output : Engineer
方法1(递归) 这个想法基于这样一个事实:一个人的职业取决于以下两个方面。
- 父母的职业。
- 节点位置:如果节点的位置是奇数,则其职业与其父节点相同。否则,这个职业就不同于它的父母。
我们递归地找到父节点的职业,然后使用上面的第2点找到当前节点的职业。 下面是上述想法的实现。
C++
// C++ program to find profession of a person at
// given level and position.
#include<bits/stdc++.h>
using
namespace
std;
// Returns 'e' if profession of node at given level
// and position is engineer. Else doctor. The function
// assumes that given position and level have valid values.
char
findProffesion(
int
level,
int
pos)
{
// Base case
if
(level == 1)
return
'e'
;
// Recursively find parent's profession. If parent
// is a Doctor, this node will be a Doctor if it is
// at odd position and an engineer if at even position
if
(findProffesion(level-1, (pos+1)/2) ==
'd'
)
return
(pos%2)?
'd'
:
'e'
;
// If parent is an engineer, then current node will be
// an engineer if at add position and doctor if even
// position.
return
(pos%2)?
'e'
:
'd'
;
}
// Driver code
int
main(
void
)
{
int
level = 4, pos = 2;
(findProffesion(level, pos) ==
'e'
)? cout <<
"Engineer"
: cout <<
"Doctor"
;
return
0;
}
JAVA
// Java program to find
// profession of a person
// at given level and position
import
java.io.*;
class
GFG
{
// Returns 'e' if profession
// of node at given level
// and position is engineer.
// Else doctor. The function
// assumes that given position
// and level have valid values.
static
char
findProffesion(
int
level,
int
pos)
{
// Base case
if
(level ==
1
)
return
'e'
;
// Recursively find parent's
// profession. If parent
// is a Doctor, this node
// will be a Doctor if it
// is at odd position and an
// engineer if at even position
if
(findProffesion(level -
1
,
(pos +
1
) /
2
) ==
'd'
)
return
(pos %
2
>
0
) ?
'd'
:
'e'
;
// If parent is an engineer,
// then current node will be
// an engineer if at add
// position and doctor if even
// position.
return
(pos %
2
>
0
) ?
'e'
:
'd'
;
}
// Driver code
public
static
void
main (String[] args)
{
int
level =
4
, pos =
2
;
if
(findProffesion(level,
pos) ==
'e'
)
System.out.println(
"Engineer"
);
else
System.out.println(
"Doctor"
);
}
}
// This code is contributed
// by anuj_67.
Python3
# python 3 program to find profession of a person at
# given level and position.
# Returns 'e' if profession of node at given level
# and position is engineer. Else doctor. The function
# assumes that given position and level have valid values.
def
findProffesion(level, pos):
# Base case
if
(level
=
=
1
):
return
'e'
# Recursively find parent's profession. If parent
# is a Doctor, this node will be a Doctor if it is
# at odd position and an engineer if at even position
if
(findProffesion(level
-
1
, (pos
+
1
)
/
/
2
)
=
=
'd'
):
if
(pos
%
2
):
return
'd'
else
:
return
'e'
# If parent is an engineer, then current node will be
# an engineer if at add position and doctor if even
# position.
if
(pos
%
2
):
return
'e'
else
:
return
'd'
# Driver code
if
__name__
=
=
'__main__'
:
level
=
3
pos
=
4
if
(findProffesion(level, pos)
=
=
'e'
):
(
"Engineer"
)
else
:
(
"Doctor"
)
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to find
// profession of a person
// at given level and position
using
System;
class
GFG
{
// Returns 'e' if profession
// of node at given level
// and position is engineer.
// Else doctor. The function
// assumes that given position
// and level have valid values.
static
char
findProffesion(
int
level,
int
pos)
{
// Base case
if
(level == 1)
return
'e'
;
// Recursively find parent's
// profession. If parent
// is a Doctor, this node
// will be a Doctor if it
// is at odd position and an
// engineer if at even position
if
(findProffesion(level - 1,
(pos + 1) / 2) ==
'd'
)
return
(pos % 2 > 0) ?
'd'
:
'e'
;
// If parent is an engineer,
// then current node will be
// an engineer if at add
// position and doctor if even
// position.
return
(pos % 2 > 0) ?
'e'
:
'd'
;
}
// Driver code
public
static
void
Main ()
{
int
level = 4, pos = 2;
if
(findProffesion(level,
pos) ==
'e'
)
Console.WriteLine(
"Engineer"
);
else
Console.WriteLine(
"Doctor"
);
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP program to find profession
// of a person at given level
// and position.
// Returns 'e' if profession of
// node at given level and position
// is engineer. Else doctor. The
// function assumes that given
// position and level have valid values.
function
findProffesion(
$level
,
$pos
)
{
// Base case
if
(
$level
== 1)
return
'e'
;
// Recursively find parent's
// profession. If parent is
// a Doctor, this node will
// be a doctor if it is at
// odd position and an engineer
// if at even position
if
(findProffesion(
$level
- 1,
(
$pos
+ 1) / 2) ==
'd'
)
return
(
$pos
% 2) ?
'd'
:
'e'
;
// If parent is an engineer, then
// current node will be an engineer
// if at odd position and doctor
// if even position.
return
(
$pos
% 2) ?
'e'
:
'd'
;
}
// Driver code
$level
= 4;
$pos
= 2;
if
((findProffesion(
$level
,
$pos
) ==
'e'
) == true)
echo
"Engineer"
;
else
echo
"Doctor"
;
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to find
// profession of a person
// at given level and position
// Returns 'e' if profession
// of node at given level
// and position is engineer.
// Else doctor. The function
// assumes that given position
// and level have valid values.
function
findProffesion(level,
pos)
{
// Base case
if
(level == 1)
return
'e'
;
// Recursively find parent's
// profession. If parent
// is a Doctor, this node
// will be a Doctor if it
// is at odd position and an
// engineer if at even position
if
(findProffesion(level - 1,
(pos + 1) / 2) == 'd
')
return (pos % 2 > 0) ?
'
d
' : '
e
';
// If parent is an engineer,
// then current node will be
// an engineer if at add
// position and doctor if even
// position.
return (pos % 2 > 0) ?
'
e
' : '
d
';
}
// Driver Code
let level = 4, pos = 2;
if(findProffesion(level,
pos) == '
e')
document.write(
"Engineer"
);
else
document.write(
"Doctor"
);
</script>
输出:
Doctor
方法2(使用位运算符)
Level 1: ELevel 2: EDLevel 3: EDDELevel 4: EDDEDEEDLevel 5: EDDEDEEDDEEDEDDE
级别输入是不必要的(如果我们忽略最大位置限制),因为第一个元素是相同的。 结果基于位置-1的二进制表示中的1计数。如果1的计数为偶数,则结果为工程师,否则为医生。 当然,位置限制是2^(1级)
C++
// C++ program to find profession of a person at // given level and position. #include<bits/stdc++.h> using namespace std; /* Function to get no of set bits in binary representation of passed binary no. */ int countSetBits( int n) { int count = 0; while (n) { n &= (n-1) ; count++; } return count; } // Returns 'e' if profession of node at given level // and position is engineer. Else doctor. The function // assumes that given position and level have valid values. char findProffesion( int level, int pos) { // Count set bits in 'pos-1' int c = countSetBits(pos-1); // If set bit count is odd, then doctor, else engineer return (c%2)? 'd' : 'e' ; } // Driver code int main( void ) { int level = 3, pos = 4; (findProffesion(level, pos) == 'e' )? cout << "Engineer" : cout << "Doctor" ; return 0; } |
JAVA
// Java program to find profession of a person at // given level and position. class GFG{ /* Function to get no of set bits in binary representation of passed binary no. */ static int countSetBits( int n) { int count = 0 ; while (n!= 0 ) { n &= (n- 1 ) ; count++; } return count; } // Returns 'e' if profession of node at given level // and position is engineer. Else doctor. The function // assumes that given position and level have valid values. static char findProffesion( int level, int pos) { // Count set bits in 'pos-1' int c = countSetBits(pos- 1 ); // If set bit count is odd, then doctor, else engineer return (c% 2 != 0 )? 'd' : 'e' ; } // Driver code public static void main(String [] args) { int level = 3 , pos = 4 ; String prof = (findProffesion(level, pos) == 'e' )? "Engineer" : "Doctor" ; System.out.print(prof); } } |
Python3
# Python3 program to find profession of a person at # given level and position. """ Function to get no of set bits in binary representation of passed binary no. """ def countSetBits(n): count = 0 while n > 0 : n & = (n - 1 ) count + = 1 return count # Returns 'e' if profession of node at given level # and position is engineer. Else doctor. The function # assumes that given position and level have valid values. def findProffesion(level, pos): # Count set bits in 'pos-1' c = countSetBits(pos - 1 ) # If set bit count is odd, then doctor, else engineer if c % 2 = = 0 : return 'e' else : return 'd' level, pos = 3 , 4 if findProffesion(level, pos) = = 'e' : print ( "Engineer" ) else : print ( "Doctor" ) # This code is contributed by divyeshrabadiya07. |
C#
using System; // c# program to find profession of a person at // given level and position. public class GFG { /* Function to get no of set bits in binary representation of passed binary no. */ public static int countSetBits( int n) { int count = 0; while (n != 0) { n &= (n - 1); count++; } return count; } // Returns 'e' if profession of node at given level // and position is engineer. Else doctor. The function // assumes that given position and level have valid values. public static char findProffesion( int level, int pos) { // Count set bits in 'pos-1' int c = countSetBits(pos - 1); // If set bit count is odd, then doctor, else engineer return (c % 2 != 0)? 'd' : 'e' ; } // Driver code public static void Main( string [] args) { int level = 3, pos = 4; string prof = (findProffesion(level, pos) == 'e' )? "Engineer" : "Doctor" ; Console.Write(prof); } } // This code is contributed by Shrikant13 |
PHP
<?php // PHP program to find profession // of a person at given level and position. // Function to get no of set // bits in binary representation // of passed binary no. function countSetBits( $n ) { $count = 0; while ( $n ) { $n &= ( $n - 1) ; $count ++; } return $count ; } // Returns 'e' if profession of // node at given level and position // is engineer. Else doctor. The // function assumes that given // position and level have valid values. function findProffesion( $level , $pos ) { // Count set bits in 'pos-1' $c = countSetBits( $pos - 1); // If set bit count is odd, // then doctor, else engineer return ( $c % 2) ? 'd' : 'e' ; } // Driver Code $level = 3; $pos = 4; if ((findProffesion( $level , $pos ) == 'e' ) == true) echo "Engineer " ; else echo "Doctor " ; // This code is contributed by aj_36 ?> |
Javascript
<script> // Javascript program to find // profession of a person at // given level and position. /* Function to get no of set bits in binary representation of passed binary no. */ function countSetBits(n) { let count = 0; while (n != 0) { n &= (n - 1); count++; } return count; } // Returns 'e' if profession of node at given level // and position is engineer. Else doctor. // The function assumes that given position and // level have valid values. function findProffesion(level, pos) { // Count set bits in 'pos-1' let c = countSetBits(pos - 1); // If set bit count is odd, then doctor, // else engineer return (c % 2 != 0)? 'd' : 'e' ; } let level = 3, pos = 4; let prof = (findProffesion(level, pos) == 'e' )? "Engineer" : "Doctor" ; document.write(prof); </script> |
输出:
Engineer
感谢Furkan Uslu提出的这种方法。 本文由 苛刻的贱民 .如果你喜欢GeekSforgek,并想贡献自己的力量,你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END